automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

, the thread automaton (plural: automata) is an extended type of

finite-state automata A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

that recognizes a mildly context-sensitive language class above the tree-adjoining languages.

Formal definition

A thread automaton consists of * a set ''N'' of states,called ''non-terminal symbols'' by Villemonte (2002), p.1r * a set Σ of terminal symbols, * a start state ''A''_''S'' ∈ ''N'', * a final state ''A''_''F'' ∈ ''N'', * a set ''U'' of path components, * a partial function δ: ''N'' → ''U''^⊥, where ''U''^⊥ = ''U'' ∪ for ⊥ ∉ ''U'', * a finite set Θ of transitions. A path ''u''₁...''u''_''n'' ∈ ''U''^* 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 closed by 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,ε,›. The final configuration is ‹''n'',''u'',›, 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'': consumes the input symbol ''a'', and changes the state of the active thread: : changes the configuration from ‹''l'',''p'',''S''∪› to ‹''l''+1,''p'',''S''∪› * SWAP ''B'' →_ε ''C'': similar, but consumes no input: : changes ‹''l'',''p'',''S''∪› to ‹''l'',''p'',''S''∪› * PUSH ''C'': creates a new subthread, and suspends its parent thread: : changes ‹''l'',''p'',''S''∪› to ‹''l'',''pu'',''S''∪› where ''u''=δ(''B'') and ''pu''∉dom(''S'') * POP 'B'''C'': ends the active thread, returning control to its parent: : changes ‹''l'',''pu'',''S''∪› to ‹''l'',''p'',''S''∪› where δ(''C'')=⊥ and ''pu''∉dom(''S'') * SPUSH 'C''''D'': resumes a suspended subthread of the active thread: : changes ‹''l'',''p'',''S''∪› to ‹''l'',''pu'',''S''∪› where ''u''=δ(''B'') * SPOP 'B''''D'': resumes the parent of the active thread: : changes ‹''l'',''pu'',''S''∪› to ‹''l'',''p'',''S''∪› where δ(''C'')=⊥ One may prove that δ(''B'')=''u'' for POP and SPOP transitions, and δ(''C'')=⊥ for SPUSH transitions.Villemonte (2002), p.1r-2r An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.

Notes

References

{{Formal languages and grammars Models of computation Automata (computation)