Thread automaton: Difference between revisions

Revision as of 14:31, 6 April 2014

Revision as of 14:36, 6 April 2014

Line 1:

In [[automata theory]], a '''thread automaton''' (plural: automata) is a [[finite-state machine|finite-state automaton]] that can make use of a thread.<ref name="eric"> {{cite journal | last = Villemonte de la Clergerie | first = Éric | year = 2002 | title = Parsing mildly context-sensitive languages with thread automata | journal = COLING '02 Proceedings of the 19th international conference on Computational linguistics | volume = 1 | issue = 3 | pages = 1–7 | issn = | url = http://delivery.acm.org/10.1145/1080000/1072256/p28-villemonte_de_la_clergerie.pdf?acc=OPEN |url=http://dl.acm.org/ft_gateway.cfm?id=1072256&ftid=256327&dwn=1&CFID=421201372&CFTOKEN=60649649| doi = 10.3115/1072228.1072256 }} </ref> Thread automata are capable of recognizing a [[mildly context-sensitive language]].

Thread automata are capable of recognizing a [[mildly context-sensitive language|mildly context-sensitive language class]] above the [[tree-adjoining grammar|tree-adjoining languages]].<ref>Villemonte (2002), p.7l</ref>

==Formal definition==