Thread automaton
In automata theory, the thread automaton (plural: automata) is an extended type of finite-state automata that recognizes a mildly context-sensitive language class above the tree-adjoining languages.^{[1]}
Formal definition
A thread automaton consists of
- a set N of states,^{[note 1]}
- 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_{1}...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_{1}...u_{n}:A, where u_{1}...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(S) is closed by prefix.
A thread automaton configuration is a triple ‹l,p,S›, where l 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 ‹0,ε,{ε:A_{S}}›. The final configuration is ‹n,u,{ε:A_{S},u:A_{F}}›, where n is the length of the input string and u abbreviates δ(A_{S}). 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:
- changes the configuration from ‹l,p,S∪{p:B}› to ‹l+1,p,S∪{p:C}›
- SWAP B →_{ε} C: similar, but consumes no input:
- changes ‹l,p,S∪{p:B}› to ‹l,p,S∪{p:C}›
- PUSH C: creates a new subthread, and suspends its parent thread:
- changes ‹l,p,S∪{p:B}› to ‹l,pu,S∪{p:B,pu:C}› where u=δ(B) and pu∉dom(S)
- POP [B]C: ends the active thread, returning control to its parent:
- changes ‹l,pu,S∪{p:B,pu:C}› to ‹l,p,S∪{p:C}› where δ(C)=⊥ and pu∉dom(S)
- SPUSH [C] D: resumes a suspended subthread of the active thread:
- changes ‹l,p,S∪{p:B,pu:C}› to ‹l,pu,S∪{p:B,pu:D}› where u=δ(B)
- SPOP [B] D: resumes the parent of the active thread:
- changes ‹l,pu,S∪{p:B,pu:C}› to ‹l,p,S∪{p:D,pu:C}› where δ(C)=⊥
One may prove that δ(B)=u for POP and SPOP transitions, and δ(C)=⊥ for SPUSH transitions.^{[2]}
An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.
Notes
- ↑ called non-terminal symbols by Villemonte (2002), p.1r
References
- ↑ Villemonte de la Clergerie, Éric (2002). "Parsing mildly context-sensitive languages with thread automata". COLING '02 Proceedings of the 19th international conference on Computational linguistics. 1 (3): 1–7. doi:10.3115/1072228.1072256. Retrieved 2016-10-15.
- ↑ Villemonte (2002), p.1r-2r