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. {{cite book | last = Villemonte de la Clergerie | first = Éric | chapter = Parsing mildly context-sensitive languages with thread automata | year = 2002 | title = Proceedings of the 19th international conference on Computational linguistics - | volume = 1 | issue = 3 |pages= 1–7 |chapter-url= http://dl.acm.org/ft_gateway.cfm?id=1072256&ftid=256327&dwn=1&CFID=421201372&CFTOKEN=60649649 |access-date= 2016-10-15 |doi= 10.3115/1072228.1072256 | doi-access = free }}
Formal definition
A thread automaton consists of
- a set N of states,called non-terminal symbols by Villemonte (2002), p.1r
- a set Σ of terminal symbols,
- a start state AS ∈ N,
- a final state AF ∈ N,
- a set U of path components,
- a partial function δ: N → U⊥, where U⊥ = U ∪ {⊥} for ⊥ ∉ U,
- a finite set Θ of transitions.
A path u1...un ∈ U* is a string of path components ui ∈ U; n may be 0, with the empty path denoted by ε.
A thread has the form u1...un:A, where u1...un ∈ 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 {{math|{{angbr|l,p,S}}}}, where {{mvar|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 {{math|{{angbr|0, ε, {{mset|ε:AS}}}}}}.
The final configuration is {{math|{{angbr|n, u, {{mset|ε:AS,u:AF}}}}}}, where n is the length of the input string and u abbreviates δ(AS).
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 {{math|{{angbr|l, p, S∪{{mset|p:B}}}}}} to {{math|{{angbr|l+1, p, S∪{{mset|p:C}}}}}}
- SWAP B →ε C: similar, but consumes no input:
: changes {{math|{{angbr|l, p, S∪{{mset|p:B}}}}}} to {{math|{{angbr|l, p, S∪{{mset|p:C}}}}}}
- PUSH C: creates a new subthread, and suspends its parent thread:
: changes {{math|{{angbr|l, p, S∪{{mset|p:B}}}}}} to {{math|{{angbr|l, pu, S∪{{mset|p:B,pu:C}}}}}} where u=δ(B) and pu∉dom(S)
- POP [B]C: ends the active thread, returning control to its parent:
: changes {{math|{{angbr|l, pu, S∪{{mset|p:B,pu:C}}}}}} to {{math|{{angbr|l, p, S∪{{mset|p:C}}}}}} where δ(C)=⊥ and pu∉dom(S)
- SPUSH [C] D: resumes a suspended subthread of the active thread:
: changes {{math|{{angbr|l, p, S∪{{mset|p:B,pu:C}}}}}} to {{math|{{angbr|l, pu, S∪{{mset|p:B,pu:D}}}}}} where u=δ(B)
- SPOP [B] D: resumes the parent of the active thread:
: changes {{math|{{angbr|l, pu, S∪{{mset|p:B,pu:C}}}}}} to {{math|{{angbr|l, p, S∪{{mset|p:D,pu:C}}}}}} where δ(C)=⊥
One may prove that δ(B)=u for POP and SPOP transitions, and δ(C)=⊥ for SPUSH transitions.Villemonte (2002), p.1r-2r
An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.
Notes
{{reflist|group=note}}