In automata theory, 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.
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,ε,{ε:AS}›.
The final configuration is ‹n,u,{ε:AS,u:AF}›, where n is the length of the input string and u abbreviates δ(AS).
[2] An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.