Informace o publikaci

Alternative Automata Characterization of Piecewise Testable Languages

Autoři

KLÍMA Ondřej POLÁK Libor

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