Informace o publikaci
Alternative Automata Characterization of Piecewise Testable Languages
| Autoři | |
|---|---|
| Rok publikování | 2013 |
| Druh | Článek ve sborníku |
| Konference | Developments in Language Theory |
| Fakulta / Pracoviště MU | |
| 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: |