CodePlexProject Hosting for Open Source Software

- Topological Sorting: an algorithm that given a directed acyclic graph
*G*produces a sequence (*v1*,...,*vk*) of all the vertices in*G*, such that, if there is an edge (*vi*,*vj*) in*G*then*i*<*j*. - Graph Partitioning: Computes an automorphism partition of an undirected simple graph. This example illustrates a nontrivial use of nested
*set*and*bag comprehensions*. The algorithm is described in Section 5 of the paper Can Abstract State Machines Be Useful in Language Theory? - Spanning Tree Computation: Illustrates
*Prim’s*algorithm. - Stopwatch Specification: Shows how an AsmL specification, containing a collection of actions, can be used to specify a finite state machine.
- Counting Problem: Shows how a
*decision problem*involving a set of prisoners and a warden can be modeled in AsmL. In general, the model has an infinite number of states. However for a given number of prisoners, the number of states is finite. The model illustrates the use of state variables with unbounded value types (in this case*integers*) and the use of state variables with rich value types (in this case*sets of integers*). - DFA Minimization: Describes a well known algorithm for minimizing a deterministic finite automaton. This example is also described in detail in the above paper.
- NFA Determinization: Describes the classical algorithm that, given a nondeterministic finite automaton, computes an equivalent deterministic finite automaton from it. This example is also described in detail in the paper mentioned above.

Last edited May 30, 2008 at 1:10 PM by araschke, version 42

In the DFA Minimization document there's an error in the final result figure, after minimizing the automaton state 4 is not an accepting state,

it should not be double circled.

it should not be double circled.