Thread automaton: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 12:03, 14 March 2014 edit Jochen Burghardt (talk \| contribs) Extended confirmed users 24,302 edits fixed broken open-access url ← Previous edit		Latest revision as of 04:47, 18 March 2025 edit undo Cedar101 (talk \| contribs) Extended confirmed users 18,557 edits m →Formal definition: {{angbr}} {{mset}}
(16 intermediate revisions by 8 users not shown)
Line 1: In [[automata theory]], athe '''thread automaton''' (plural: automata) is aan extended type of [[finite-state machine\|finite-state ~~automaton~~automata]] that ~~can~~recognizes ~~make~~a ~~use~~[[mildly ofcontext-sensitive alanguage ~~thread~~class]] above the [[tree-adjoining grammar\|tree-adjoining languages]].<ref name="eric"> {{cite ~~journal~~book \| last = Villemonte de la Clergerie \| first = Éric \| ~~year = 2002 \| title~~chapter = Parsing mildly context-sensitive languages with thread automata \| ~~journal~~year = ~~COLING~~2002 ~~'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= 2016-10-15 \|doi = 10.3115/1072228.1072256 \| doi-access = free }} </ref> ~~Thread automata are capable of recognizing a [[mildly context-sensitive language]].~~ ==~~See~~Formal ~~also~~definition== * [[Automata theory]] A '''thread automaton''' consists of * a set ''N'' of states,<ref group=note>called ''non-terminal symbols'' by Villemonte (2002), p.1r</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 [[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 {{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> 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}} ==References== {{reflist}} ~~<references/>~~ {{Formal languages and grammars}} ~~{{comp-sci-stub}}~~ [[Category:Models of computation]] [[Category:Automata ~~theory~~(computation)]]