Publication details
Alternative Automata Characterization of Piecewise Testable Languages
Authors | |
---|---|
Year of publication | 2013 |
Type | Article in Proceedings |
Conference | Developments in Language Theory |
MU Faculty or unit | |
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: |