Thread automaton (Ofer Abarbanel online library)

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

thread automaton consists of

  • a set Nof states,[note 1]
  • a set Σ of terminal symbols,
  • a start state AS∈ N,
  • a final state AF∈ N,
  • a set Uof path components,
  • a partial function δ: N→ U, where U = U ∪ {⊥} for ⊥ ∉ U,
  • a finite set Θ of transitions.

path u1un ∈ U* is a string of path components ui ∈ Un may be 0, with the empty path denoted by ε. A thread has the form u1un:A, where u1un ∈ 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,ε,{ε:AS}›. The final configuration is ‹n,u,{ε:AS,u:AF}›, where n is the length of the input string and u abbreviates δ(AS). A transition in the set Θ may have one of the following forms, and changes the current automaton configuration in the following way:

  • SWAPB →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}›

  • SWAPB →ε C:   similar, but consumes no input:

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

  • PUSHC:   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[CD:   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[BD:   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.


  1. ^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.
  2. ^Villemonte (2002), p.1r-2r

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library