Examining automata

The following outlines ways of examining automata.

Most operations for examining automata are generic and rely on the intrinsic operations. However, some operations can be optimised for certain types of automata, and then have different performance characteristics.

Drawing an automaton

The Flipsta library cannot actually draw automata; but it can produce .dot files that are straightforward to convert into, say, PDF or SVG, using Graphviz dot.

template <class Automaton>
void draw(std::ostream & file, Automaton const & automaton, bool horizontal = false)

Produce a .dot file for Graphviz dot to convert into a graphical representation.

The names of states are put inside the nodes; the start and end labels, if any, go next to it. This uses the “xlabel” attribute and requires dot version 2.28 to render. Earlier versions leave out the labels.

The textual representation of states and labels is acquired by streaming them into an ostream.

Assuming the Graphviz dot is installed, then after writing the textual representation to automaton.dot, saying the following on the command line will convert it into a PDF file:

dot -Tpdf automaton.dot -o automaton.pdf

Parameters
  • file -

    The ostream to output the textual representation to.

  • automaton -

    The automaton to be drawn.

  • horizontal -

    Lay levels out horizontally instead of vertically.

Traversing an automaton

For various algorithms it is important to traverse automata in a specific order. For example, finding the shortest distance in an acyclic automaton traverses the automaton in topological order. The standard algorithm for finding the topological order uses depth-first traversal.

The standard return value for a function that traverses an automaton is a, possibly lazy, range of states. (Using callback functions would be possible, but this would be more cumbersome to use.)

Topological order

A topological order is an order of the states of an automaton in which for each transition the source comes before the destination. It is possible to order the states iff the automaton is acyclic.

auto constexpr topologicalOrder

Return the states of the automaton in topological order.

This may be computed lazily. The automaton must remain in memory and unaltered while the range that is returned is being used.

The standard implementation holds a container of arcs. It is implemented iff traverse is implemented for the automaton and the direction. It takes linear time in the number of transitions and linear space in the number of states to build this.

A specialised implementation can be provided for some automata. An example is automata based on products of automata, for which this can be a lazy list which takes up less space.

Parameters
  • automaton -

    Pointer to the automaton to find the topological order of. If the order is computed lazily, then a copy of this pointer may be kept until the result type is destructed.

  • direction -

    The direction to use, of type Forward or Backward.

Exceptions
  • AutomatonNotAcyclic -

    Iff the automaton is not acyclic (so that topological order is not defined). In the default implementation, the exception will have errorInfoState <State> attached to it with the state that was detected to have a path to itself. The exception may be thrown during traversal.

Depth-first traversal

A basic way to traverse an automaton is depth-first search.

template <class AutomatonPtr, class Direction>
auto traverse(AutomatonPtr && automaton, Direction direction)

Traverse the automaton and return (lazily) a range of states marked with their meaning.

The automaton must remain unchanged while the resulting range is being used. The range is non-copyable but it is moveable.

This uses “depth-first search” (for those in the know) to find a spanning forest, and keeps going until the each state have been tried as roots. (Either the state has been seen before, or it is the root of a new tree.) The elements of the resulting range are of type TraversedState <State>. This contains a state, and an enum indicating what stage of traversal the state was involved in. Usually you will want to filter only elements with a limited sets of indicator.

If you do not know how depth-first search works, here is what you need to know to use this function.

  • newRoot is emitted once for each root of a tree. This will happen at least once, and it may happen for each state. If the states are in a topological order, then this will happen once. The next event emitted will be the same state, with visit.
  • visit is emitted exactly once for each state, when it is first discovered.
  • finishVisit is emitted exactly once for each state, when the visit to it finishes. Since states are visited recursively, the order of states with finishVisit will be different from the order of those with visit. The order of the states with finishVisit is reverse topological order.
  • backState is emitted when a state is rediscovered that is being visited. If this occurs at all, the automaton has at least as many cycles as this occurs. If this does not occur, the automaton is acyclic.
  • forwardOrCrossState is emitted when a state is rediscovered that has been visited. It may be part of the same tree or in a different one. (More detailed classification is possible, but would take time and is not that useful.)
The number of elements in the returned range, and the total time complexity, is \Theta(n) where n is the number of states in the automaton. While the returned range is being consumed, space use also rises to \Theta(n).

The automaton must have states() and arcsOnCompressed.

Parameters
  • automaton -

    Pointer to the automaton to traverse. A copy of the pointer will be kept, and destructed when the range is destructed. This can be a unique_ptr. The automaton should not change while the range is used.

Parameters
  • direction -

    The direction in which to traverse the automaton.

template <class State>
struct flipsta::TraversedState

Event generated while traversing an automaton using depth-first search.

Public Members

State state

The state that this event concerns.

TraversalEvent event

The type of event.

TraversalEvent enum

Indicate the meaning of the state during depth-first traversal.

Values:

  • newRoot -

    Indicates the state will be the root of a tree.

  • visit -

    Indicates that a newly discovered state is now being visited.

  • finishVisit -

    Indicates that the visit to the state has finished.

  • backState -

    Indicates that the state was rediscovered while it was being visited.

  • forwardOrCrossState -

    Indicates that the state was rediscovered while it was not being visited any more.

Table Of Contents

Previous topic

Automata

Next topic

Shortest-distance algorithms

This Page