This page is in very early stage of writing. It's most prominent feature is its incompleteness.

accessible (or reachable, or initially connected)

A state $s$ is accessible if there is a path from an initial state to $s$.

An automaton is /accessible/ if all its states are.


Antimirov automaton

See derived-term automaton.

derived-term automaton

See expression.derived_term.

equation automaton

See derived-term automaton.


A lightening cycle is a path from a state to itself that is either negative (for $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{Z}$), or between 0 and 1 (for $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{R}_\text{min}$).


A valueset is commutative if mul(u, v) == mul(v, u).


A labelset is free if the labels are only "letters". This is a requirement for algorithms such as determinize, evaluate.

  • letterset is free.
  • nullableset is not free.
  • oneset is not free.
  • wordset is not free.
  • tupleset is free if its components are free.

If the labelset is free, then label_t is letter_t.


A valueset is idempotent if add(v, v) == v.


A labelset is letterized if it free, or nullable of free. In other words, its labels are either letters, or the empty word. Maybe surprisingly, oneset ($\{1\}$) is letterized.

partial-derivative automaton

See derived-term automaton.

position automaton

See standard automaton.