Thread automaton: Difference between revisions

Revision as of 05:38, 7 May 2014

Latest revision as of 04:47, 18 March 2025

(9 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 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 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,

Line 13 ⟶ 12:

* a finite set Θ of transitions.

A '''path''' ''u''₁...''u''_''n'' ∈ ''U''^{[[Kleene star|*]]} is a string of path components ''u''_''i'' ∈ ''U''; ''n'' may be 0, with the empty path denoted by ε.

A '''thread''' has the form ''u''₁...''u''_''n'':''A'', where ''u''₁...''u''_''n'' ∈ ''U''^* 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''^* 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''_''S''}›}}}}}.

The '''final configuration''' is ‹{{math|{{angbr|''n'', ''u'', {{mset|ε:''A''_''S'',''u'':''A''_''F''}›}}}}}, where ''n'' is the length of the input string and ''u'' abbreviates δ(''A''_''S'').

A '''transition''' in the set Θ may have one of the following forms, and changes the current automaton configuration in the following way:

* '''SWAP''' ''B'' →_''a'' ''C'': &nbsp; consumes the input symbol ''a'', and changes the state of the active thread:

: changes the configuration from &nbsp; ‹{{math|{{angbr|''l'', ''p'', ''S''∪{{mset|''p'':''B''}›}}}}} &nbsp; to &nbsp; ‹{{math|{{angbr|''l''+1, ''p'', ''S''∪{{mset|''p'':''C''}›}}}}}

* '''SWAP''' ''B'' →_ε ''C'': &nbsp; similar, but consumes no input:

: changes &nbsp; ‹{{math|{{angbr|''l'', ''p'', ''S''∪{{mset|''p'':''B''}›}}}}} &nbsp; to &nbsp; ‹{{math|{{angbr|''l'', ''p'', ''S''∪{{mset|''p'':''C''}›}}}}}

* '''PUSH''' ''C'': &nbsp; creates a new subthread, and suspends its parent thread:

: changes &nbsp; ‹{{math|{{angbr|''l'', ''p'', ''S''∪{{mset|''p'':''B''}›}}}}} &nbsp; to &nbsp; ‹{{math|{{angbr|''l'', ''pu'', ''S''∪{{mset|''p'':''B'',''pu'':''C''}›}}}}} &nbsp; where ''u''=δ(''B'') and ''pu''∉dom(''S'')

* '''POP''' [''B'']''C'': &nbsp; ends the active thread, returning control to its parent:

: changes &nbsp; ‹{{math|{{angbr|''l'', ''pu'', ''S''∪{{mset|''p'':''B'',''pu'':''C''}›}}}}} &nbsp; to &nbsp; ‹{{math|{{angbr|''l'', ''p'', ''S''∪{{mset|''p'':''C''}›}}}}} &nbsp; where δ(''C'')=⊥ and ''pu''∉dom(''S'')

* '''SPUSH''' [''C''] ''D'': &nbsp; resumes a suspended subthread of the active thread:

: changes &nbsp; ‹{{math|{{angbr|''l'', ''p'', ''S''∪{{mset|''p'':''B'',''pu'':''C''}›}}}}} &nbsp; to &nbsp; ‹{{math|{{angbr|''l'', ''pu'', ''S''∪{{mset|''p'':''B'',''pu'':''D''}›}}}}} &nbsp; where ''u''=δ(''B'')

* '''SPOP''' [''B''] ''D'': &nbsp; resumes the parent of the active thread:

: changes &nbsp; ‹{{math|{{angbr|''l'', ''pu'', ''S''∪{{mset|''p'':''B'',''pu'':''C''}›}}}}} &nbsp; to &nbsp; ‹{{math|{{angbr|''l'', ''p'', ''S''∪{{mset|''p'':''D'',''pu'':''C''}›}}}}} &nbsp; 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==

Line 44 ⟶ 43:

{{Formal languages and grammars}}

{{comp-sci-stub}}

[[Category:Models of computation]]

[[Category:Automata theory(computation)]]