Alternative Automata Characterization of Piecewise Testable Languages

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.

Autoři	KLÍMA Ondřej POLÁK Libor
Rok publikování	2013
Druh	Článek ve sborníku
Konference	Developments in Language Theory
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
Doi	http://dx.doi.org/10.1007/978-3-642-38771-5_26
Obor	Obecná matematika
Klíčová slova	piecewise testable languages; acyclic automata; locally con- fluent automata
Popis	We present a transparent condition on a minimal automaton which is equivalent to piecewise testability of the corresponding regular language. The condition simplifies the original Simon’s condition on the minimal automaton in a different way than conditions of Stern and Trahtman. Secondly, we prove that every piecewise testable language L is k-piecewise testable for k equal to the depth of the minimal DFA of L. This result improves all previously known estimates of such k.
Související projekty:	Centrum excelence - Institut teoretické informatiky