Alternative Automata Characterization of Piecewise Testable Languages

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KLÍMA Ondřej POLÁK Libor

Year of publication 2013
Type Article in Proceedings
Conference Developments in Language Theory
MU Faculty or unit

Faculty of Science

Citation
Doi http://dx.doi.org/10.1007/978-3-642-38771-5_26
Field General mathematics
Keywords piecewise testable languages; acyclic automata; locally con- fluent automata
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info