# Thread automaton

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.^{[1]}

## Formal definition[edit]

A **thread automaton** consists of

- a set
*N*of states,^{[note 1]} - 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 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:

**SWAP***B*→_{a}*C*: consumes the input symbol*a*, and changes the state of the active thread:

- changes the configuration from ‹
*l*,*p*,*S*∪{*p*:*B*}› to ‹*l*+1,*p*,*S*∪{*p*:*C*}›

**SWAP***B*→_{ε}*C*: similar, but consumes no input:

- changes ‹
*l*,*p*,*S*∪{*p*:*B*}› to ‹*l*,*p*,*S*∪{*p*:*C*}›

**PUSH***C*: creates a new subthread, and suspends its parent thread:

- changes ‹
*l*,*p*,*S*∪{*p*:*B*}› to ‹*l*,*pu*,*S*∪{*p*:*B*,*pu*:*C*}› where*u*=δ(*B*) and*pu*∉dom(*S*)

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

- changes ‹
*l*,*pu*,*S*∪{*p*:*B*,*pu*:*C*}› to ‹*l*,*p*,*S*∪{*p*:*C*}› where δ(*C*)=⊥ and*pu*∉dom(*S*)

**SPUSH**[*C*]*D*: resumes a suspended subthread of the active thread:

- changes ‹
*l*,*p*,*S*∪{*p*:*B*,*pu*:*C*}› to ‹*l*,*pu*,*S*∪{*p*:*B*,*pu*:*D*}› where*u*=δ(*B*)

**SPOP**[*B*]*D*: resumes the parent of the active thread:

- changes ‹
*l*,*pu*,*S*∪{*p*:*B*,*pu*:*C*}› to ‹*l*,*p*,*S*∪{*p*:*D*,*pu*:*C*}› where δ(*C*)=⊥

One may prove that δ(*B*)=*u* for **POP** and **SPOP** transitions, and δ(*C*)=⊥ for **SPUSH** transitions.^{[2]}

An input string is **accepted** by the automaton if there is a sequence of transitions changing the initial into the final configuration.

## Notes[edit]

**^**called*non-terminal symbols*by Villemonte (2002), p.1r

## References[edit]

**^**Villemonte de la Clergerie, Éric (2002). "Parsing mildly context-sensitive languages with thread automata".*COLING '02 Proceedings of the 19th international conference on Computational linguistics*.**1**(3): 1–7. doi:10.3115/1072228.1072256. Retrieved 2016-10-15.**^**Villemonte (2002), p.1r-2r