Alternative Automata Characterization of Piecewise Testable Languages

Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info