List of Sample Specifications
=============================


AnBnCn: Generates Language of A^n B^n C^n
-----------------------------------------

Strings of the form aabbcc, aaabbbcc, ... are represented as
as graphs, where each character is a node and where 'next' edges
are used to connect nodes such that they form the required sentence.

The specification shows four different ways how to generate the
language of all sentences which have the same number of a, b, and
c characters:

1) A straightforward solution based on graph rewrite rules
   where left- and right-hand side share nodes.

2) A "beautiful" solution with the same type of graph rewrite
   rules as above and with path expressions.

3) A tricky solution with CONTEXT-FREE graph rewrite rules, where
   left-hand sides consist of a single (nonterminal) node and
   where embedding rules do the main work.

4) A last solution based on parallel graph rewriting (a single
   rewrite rule is applied to all occurrences of its left-hand
   side simultaneously).


CIM: Computer-Integrated-Manufacturing Management Specification
---------------------------------------------------------------

A specification of a (very) simple CIM management tool which
keeps track of used development tools, workstations, and documents
and the relationships between them.


Colouring: Constraint Solving Algorithms for Map Colouring
----------------------------------------------------------

The specification shows four different ways to solve the well-known
map colouring problem (with four colours). Used algorithms are:

1) Generate colour assigment and test correctness.

2) Backtracking: Generate, test, and extend partial colour
   assigments.

3) Forward checking: a more sophisticated constraint solving
   algorithm which restricts colour sets of neighbours of
   countries with fixed colour.

4) Look ahead: a even more sophisticated constraint solving
   algorithm which restricts colour sets of direct and indirect
   neighbours of countries with fixed colour.


CSPwithFC: Constraint Solving Algorithm for n-Queen-Problem
-----------------------------------------------------------

The specification uses again a forward checking algorithm to
solve the well-known problem to position n queens on a n x n
chess board such that these queens do not attack each other.
It is mainly used a test of the recently introduced cut-
operator in PROGRES.,


FOCS: Feature Oriented Classification System
--------------------------------------------

This is the specification of a database of reusable software
components. It offers operations for

* the development of classification schemes

* the classification of software components and documentation

* retrieval of software components

* management of database system users

It is our main example for demonstrating the rapid prototyping
functionality of PROGRES. A generated FOCS prototype is part of the
release. It offers different categories of users parallel access to
a common reuse database.


FerryMan: The well-known AI problem ...
---------------------------------------

This the running example of the GUIDED TOUR through the PROGRES
environment. It shows very well PROGRES ability of depth-first
search and backtracking, i.e. its rule-oriented way to solve AI
problems.


JungleRewriting: Simplification of Expression Trees
---------------------------------------------------

The specification takes a simple arithmetic expression as input
and produces a simplified expression as output. Simplification rules
include

* elimination of "add 0 to" or "multiply by 1"

* sharing of common subexpression

The result is no longer a tree, but a directed acyclic graph (jungle)
due to sharing of subexpressions.

The main purpose of this specification is to demonstrate PROGRES
way of nonisomorphic subgraph rewriting. It contains some graph rewrite
rules with a "FOLDING" pragma. This pragma allows certain nodes in
left-hand sides to match the same node in a host graph.


MILEditor: Module Interconnection Language Editor
-------------------------------------------------

This is the specification of a graphical editor for software designs.
Software designs may contain three different types of modules. Each
module may have a number of associated implementation variants with
different properties and import relationships.

A depth-first search and backtracking process is used to construct
consistent and complete system configurations with required properties:

* One variant of the system's main module with required properties is
  part of the computed configuration

* The configuration contains a single variant with the required properties
  for each import of each variant which is part of the configuration

* The configuration contains only variants of modules which are directly
  or indirectly imported by the selected main module variant


MedicalDiagnosisSystem: A Knowledge Based Database System for Practices
-----------------------------------------------------------------------

The specification of a medical database system with the following data:

* Doctors and patients in practice

* Treatments, prescriptions etc. for patients

* Knowlege about diseases and their symptoms, etc.


Phascum Cuspidatum: Models the Development Process of a Moss
------------------------------------------------------------

The development process of the moss Phascum Cuspidatum is one of
the standard examples of the literature about L(indenmeyer) systems.
L systems are closely related to parallel graph rewriting systems.
A first? specification of the development process of P.C. by
means of parallel graph rewriting systems was published in

M. Nagl: Graphgrammatiken, Vieweg Verlag (1979)

The PROGRES specification is a more or less literal translation of
the original specification. It shows how parallel graph rewriting may
be simulated (to a certain extent) in PROGRES by using "star" rules
which are applied to all occurrences of their left-hand sides in
a single rewrite step.


P(recedence)Net(work)s: Simple Task and Resource Management Tool
----------------------------------------------------------------

This is the specification of a task and resource management tool.
It supports editing task networks (with precedence relationships
between them) as well as computing minimal execution times and
critical paths. The specified tool supports also assignment of
resources to tasks and checks/resolves resource conflicts.


RedBlackTrees: Specification Height-Balanced Binary Search Trees
----------------------------------------------------------------

This is an example of a well-known abstract data type specification.
The data structure is a height-balanced search tree with two types of
edges (red/black): 

* The number of black edges from the tree's root to a leaf is always
  the same

* No path from a tree root to tree leaf has to red edges where the
  target of the first one is the source of the next one.

The "kernel" of the specification are four tree rotating graph rewrite
rules for rebalancing forbidden subtrees.


ResistorNets: Creating, Analyzing, and Simplifying ResistorNets
---------------------------------------------------------------

 ...


SampleImport: Import of externally defined types in PROGRES
-----------------------------------------------------------

The specification is our main example for demonstrating the usage of
external/imported attribute types in specifications. These types are
implemented in C (following certain conventions) and dynamically linked
at runtime to the PROGRES environment executable.


TBTree: Threaded Binary Trees
-----------------------------

Another example of a well-known data structure. Threaded binary trees
are binary search trees where all stored elements (nodes) form a sorted
list (via additional next edges).


nDimCube: Generating (Hyper-)Cubes of Dimension n = 1, 2, 3, ...
----------------------------------------------------------------

This a very compact specification of the language (class of graphs)
of all hypercubes. It is another example for the PARALLEL application
of graph rewrite rules to all occurrences in graph (instead of the
default application to a nondeterministically selected single occurrence).
