Content deleted Content added
fixed broken open-access url |
→top: started section "Formal Definition" |
||
Line 1:
In [[automata theory]], a '''thread automaton''' (plural: automata) is a [[finite-state machine|finite-state automaton]] that can make use of a thread.<ref name="eric"> {{cite journal | last = Villemonte de la Clergerie | first = Éric | year = 2002 | title = Parsing mildly context-sensitive languages with thread automata | journal = COLING '02 Proceedings of the 19th international conference on Computational linguistics | volume = 1 | issue = 3 | pages = 1–7 | issn = | 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| doi = 10.3115/1072228.1072256 }} </ref> Thread automata are capable of recognizing a [[mildly context-sensitive language]].
==Formal definition==
A thread automaton consists of
* a set ''N'' of states,<ref group=note>called ''non-terminal symbols'' by Villemonte</ref>
* a set Σ of terminal symbols,
* a start state ''A''<sub>''S''</sub> ∈ ''N'',
* a final state ''A''<sub>''F''</sub> ∈ ''N'',
* a set ''U'' of path components,
* a partial function δ: ''N'' → ''U''<sup>⊥</sup>, where ''U''<sup>⊥</sup> = ''U'' ∪ {⊥} for ⊥ ∉ ''U'',
* a finite set Θ of transitions.
A path ''u''<sub>1</sub>...''u''<sub>''n''</sub> ∈ ''U''<sup>[[Kleene star|*]]</sup> is a string of path components ''u''<sub>''i''</sub> ∈ ''U''; ''n'' may be 0, with the empty path denoted by ε.
A thread has the form ''u''<sub>1</sub>...''u''<sub>''n''</sub>:''A'', where ''u''<sub>1</sub>...''u''<sub>''n''</sub> ∈ ''U''<sup>*</sup> 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''<sup>*</sup> to ''N'', such that ''dom''(''S'') is closed by [[prefix (computer science)|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''<sub>''S''</sub>}›.
The final configuration is ‹''n'',''u'',{ε:''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 ‹''l'',''p'',''S''∪{''p'':''B''}› to ‹''l''+1,''p'',''S''∪{''p'':''C''}›
* '''SWAP''' ''B'' →<sub>ε</sub> ''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.
An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.
==See also==
| |||