This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0037721302 Reproduction Date:
In automata theory, a thread automaton (plural: automata) is a finite-state automaton that can make use of a thread.^{[1]} Thread automata are capable of recognizing a mildly context-sensitive language class above the tree-adjoining languages.^{[2]}
A thread automaton consists of
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 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,ε,{ε:A_{S}}›. The final configuration is ‹n,u,{ε: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:
One may prove that δ(B)=u for POP and SPOP transitions, and δ(C)=⊥ for SPUSH transitions.^{[3]}
An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.
Computer science, Mathematics, Artificial intelligence, Theory of computation, Numerical analysis
Context-free grammar, Nested word, Chomsky hierarchy, Linear context-free rewriting system, Indexed grammar
Computer science, Automata theory, Formal language, String (computer science), Nondeterministic finite automaton
Linguistics, Biology, Artificial intelligence, Turing machine, Computer science
Logic, Semantics, String (computer science), Mathematical logic, Computer science
Nested word, Ptime, Automata theory, Formal language, Formal grammar
Automata theory, Nested word, Transition monoid, Regular language, Star-free language
Tree-adjoining grammar, Nested word, Context-free grammar, Pushdown automaton, Context-sensitive grammar
Formal grammar, Theoretical computer science, Regular language, Nested word, Regular expression