Thread automaton

In automata theory, the thread automaton is an extended type of finite-state automata that recognizes a mildly context-sensitive language class above the tree-adjoining languages.

Formal definition

A thread automaton consists of

a set N of states,
a set Σ of terminal symbols,
a start state A_S ∈ N,
a final state A_F ∈ N,
a set U of path components,
a partial function δ: N → U^⊥, where U^⊥ = U ∪ for ⊥ ∉ U,
a finite set Θ of transitions.

A path u₁...u_n ∈ U^* is a string of path components u_i ∈ U; n may be 0, with the empty path denoted by ε.
A thread has the form u₁...u_n:A, where u₁...u_n ∈ U^* is a path, and A ∈ N is a state.
A thread store S is a finite set of threads, viewed as a partial function from U^* to N, such that dom is closed by prefix.
A thread automaton configuration is a triple, where denotes the current position in the input string, p is the active thread, and S is a thread store containing p.
The initial configuration is.
The final configuration is, where n is the length of the input string and u abbreviates δ.
A transition in the set Θ may have one of the following forms, and changes the current automaton configuration in the following way:SWAP B →_a C: consumes the input symbol a, and changes the state of the active thread:SWAP B →_ε C: similar, but consumes no input:PUSH C: creates a new subthread, and suspends its parent thread:POP C: ends the active thread, returning control to its parent:SPUSH D: resumes a suspended subthread of the active thread:SPOP D: resumes the parent of the active thread:
One may prove that δ=u for POP and SPOP transitions, and δ=⊥ for SPUSH transitions.
An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.