Thread automaton: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 20:12, 17 December 2018 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,633 edits not a stub ← 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}}
(3 intermediate revisions by 2 users not shown)
Line 1: In [[automata theory]], the '''thread automaton''' (plural: automata) is an extended type of [[finite-state machine\|finite-state automata]] that recognizes a [[mildly context-sensitive language 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 \|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 }} </ref> ==Formal definition== Line 16: 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>