Thread automaton

百度回乡29年,甘祖昌和乡亲们一起,自力更生,艰苦奋斗,修建了3座水库、25公里长的渠道、4座水电站、3条公路、12座桥梁,为促进家乡的经济发展作出了很大贡献。

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

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₁...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₁...u_n:A, where u₁...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 \cup{p : B}?

to

? l +1, p, S \cup{p : C}?

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

changes

? l, p, S \cup{p : B}?

to

? l, p, S \cup{p : C}?

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

changes

? l, p, S \cup{p : B}?

to

? l, pu, S \cup{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 \cup{p : B, pu : C}?

to

? l, p, S \cup{p : C}?

where δ(C)=⊥ and pu?dom(S)

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

changes

? l, p, S \cup{p : B, pu : C}?

to

? l, pu, S \cup{p : B, pu : D}?

where u=δ(B)

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

changes

? l, pu, S \cup{p : B, pu : C}?

to

? l, p, S \cup{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

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

References

^ Villemonte de la Clergerie, éric (2002). "Parsing mildly context-sensitive languages with thread automata". Proceedings of the 19th international conference on Computational linguistics -. Vol. 1. pp. 1–7. doi:10.3115/1072228.1072256. Retrieved 2025-08-06.
^ Villemonte (2002), p.1r-2r

[2] non-terminal symbols by Villemonte (2002), p.1r

[eric-1] Villemonte de la Clergerie, éric (2002). "Parsing mildly context-sensitive languages with thread automata". Proceedings of the 19th international conference on Computational linguistics -. Vol. 1. pp. 1–7. doi:10.3115/1072228.1072256. Retrieved 2025-08-06.

[3] Villemonte (2002), p.1r-2r

[1]

[note 1]

[2]

胃痛看什么科	甲胎蛋白偏高说明什么	7月16日什么星座	从头再来什么意思	4月29是什么星座
脚底干裂起硬皮是什么原因怎么治	蓝痣有没有什么危害	朋友梦到我怀孕了是什么意思	42天产后检查挂什么科	心肌缺血吃什么药好
妈妈桑是什么意思	胃酸胃烧心吃什么药	牌匾是什么意思	脑梗死是什么意思	衤字旁的字与什么有关
rf是什么的缩写	11.4什么星座	百年好合是什么意思	1994年属狗五行属什么	尾椎骨疼痛是什么原因

检查膝盖挂什么科hcv9jop7ns9r.cn	很多条腿的虫子叫什么hcv8jop1ns6r.cn	光明会到底是干什么的hcv8jop6ns6r.cn	为什么天天做梦hcv9jop1ns9r.cn	爽约是什么意思96micro.com
主任科员是什么级别hcv9jop3ns5r.cn	付之一炬什么意思hcv8jop7ns4r.cn	牙周炎用什么漱口水好hcv7jop6ns3r.cn	痔疮最怕吃什么mmeoe.com	了了什么意思hcv7jop6ns1r.cn
头痛呕吐什么原因hcv9jop1ns0r.cn	腱鞘炎是什么hcv9jop2ns1r.cn	猪润是什么hcv7jop6ns5r.cn	刘邦是汉什么帝hcv9jop0ns6r.cn	度化是什么意思hcv8jop7ns1r.cn
送镜子代表什么意思hcv8jop9ns9r.cn	吃什么水果能变白1949doufunao.com	嬴稷是秦始皇的什么人hcv7jop6ns8r.cn	什么是脑梗塞hcv9jop6ns9r.cn	便秘吃什么xianpinbao.com