In
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 with close connections to cognitive science and mathematical l ...
, the thread automaton (plural: automata) is an extended type of
finite-state automata 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''
1...''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''
1...''u''
''n'':''A'', where ''u''
1...''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 prefix is an affix which is placed before the stem of a word. Particularly in the study of languages, a prefix is also called a preformative, because it alters the form of the word to which it is affixed.
Prefixes, like other affixes, can b ...
.
A thread automaton configuration is a triple , where 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 .
The final configuration is , 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 to
* SWAP ''B'' →
ε ''C'': similar, but consumes no input:
: changes to
* PUSH ''C'': creates a new subthread, and suspends its parent thread:
: changes to where ''u''=δ(''B'') and ''pu''∉dom(''S'')
* POP
'B'''C'': ends the active thread, returning control to its parent:
: changes to where δ(''C'')=⊥ and ''pu''∉dom(''S'')
* SPUSH
'C''''D'': resumes a suspended subthread of the active thread:
: changes to where ''u''=δ(''B'')
* SPOP
'B''''D'': resumes the parent of the active thread:
: changes to 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)