Thread automaton

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 u1...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 u1...u**n:A, where u1...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 , 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 . 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.

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

Notes

References

References

1. Villemonte de la Clergerie, Éric. (2002). "Proceedings of the 19th international conference on Computational linguistics -".
2. Villemonte (2002), p.1r-2r