pre-automaton, quasi-automaton
pre-automatonとは、始状態も終状態も持たない(Σ, S, δ)のことらしい。これはラベル付き遷移系と同じだと思う。
"Monadic SecondOrder Logic, Graphs and Unfoldings of Transition Systems"から:
Let n, m ∈N and m ≧ 1. A transition system of type (n, m) is a tuple R = (G, x, P1, ...,Pn, Q1, ...,Qm), where G is a directed graph, x is a vertex called the root of R from which all other vertices are accessible by a directed path, P1, ...,Pn are sets of vertices and Q1, ...,Qm is a partition of the set of edges.
A vertex of G is called a state of R and an edge is called a transition. A transition in Qi is said to be of type i.
A quasi-automaton is a pair A = (A, Ω) where A is a (possibly infinite) transition system of type (n, 2), for some n, and Ω is a function assigning a natural number from a finite set to every node of A. We require that the image of Ω is finite.
いまいちわからん。