Revision as of 14:31, 8 November 2024 edit Citation bot (talk \| contribs) Bots 5,864,538 edits Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. \| Use this bot. Report bugs. \| Suggested by Dominic3203 \| Category:Models of computation \| #UCB_Category 18/125 ← 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}}
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>

Thread automaton: Difference between revisions