|
In [[automata theory]], athe '''thread automaton''' (plural: automata) is aan extended type of [[finite-state machine|finite-state automatonautomata]] that canrecognizes makea use[[mildly ofcontext-sensitive alanguage threadclass]] above the [[tree-adjoining grammar|tree-adjoining languages]].<ref name="eric"> {{cite journalbook | last = Villemonte de la Clergerie | first = Éric | year = 2002 | titlechapter = Parsing mildly context-sensitive languages with thread automata | journalyear = COLING2002 '02| title = Proceedings of the 19th international conference on Computational linguistics - | volume = 1 | issue = 3 | pages = 1–7 | issn = | chapter-url = http://delivery.acm.org/10.1145/1080000/1072256/p28-villemonte_de_la_clergerie.pdf?acc=OPEN |url=http://dl.acm.org/ft_gateway.cfm?id=1072256&ftid=256327&dwn=1&CFID=421201372&CFTOKEN=60649649 |access-date= doi2016-10-15 |doi= 10.3115/1072228.1072256 | doi-access = free }} </ref>
Thread automata are capable of recognizing a [[mildly context-sensitive language class]] above the [[tree-adjoining grammar|tree-adjoining languages]].<ref>Villemonte (2002), p.7l</ref>
==Formal definition==
A '''thread store''' ''S'' is a finite set of threads, viewed as a partial function from ''U''<sup>*</sup> to ''N'', such that ''dom''(''S'') is [[closure (mathematics)|closed]] by [[prefix (computer science)|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 ‹0{{math|{{angbr|0, ε, {{mset|ε:''A''<sub>''S''</sub>}›}}}}}.
The '''final configuration''' is ‹{{math|{{angbr|''n'', ''u'', {{mset|ε:''A''<sub>''S''</sub>,''u'':''A''<sub>''F''</sub>}›}}}}}, where ''n'' is the length of the input string and ''u'' abbreviates δ(''A''<sub>''S''</sub>).
A '''transition''' in the set Θ may have one of the following forms, and changes the current automaton configuration in the following way:
* '''SWAP''' ''B'' →<sub>''a''</sub> ''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'' →<sub>ε</sub> ''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.<ref>Villemonte (2002), p.1r-2r</ref>
{{Formal languages and grammars}}
{{comp-sci-stub}}
[[Category:Models of computation]]
[[Category:Automata theory(computation)]]
| 