Examples

This is a collection of samples showing various ways of using AsmL. The samples are given as word documents in form of executable specifications with embedded AsmL code that can be executed directly from the documents.

• 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.