Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1164086,
author = {Klíma, Ondřej and Polák, Libor},
address = {Berlin Heidelberg},
booktitle = {Developments in Language Theory},
doi = {http://dx.doi.org/10.1007/978-3-642-38771-5_26},
editor = {Marie-Pierre Béal, Olivier Carton},
keywords = {piecewise testable languages; acyclic automata; locally con- fluent automata},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin Heidelberg},
isbn = {978-3-642-38770-8},
pages = {289-300},
publisher = {Springer-Verlag},
title = {Alternative Automata Characterization of Piecewise Testable Languages},
year = {2013}
}
TY - JOUR
ID - 1164086
AU - Klíma, Ondřej - Polák, Libor
PY - 2013
TI - Alternative Automata Characterization of Piecewise Testable Languages
PB - Springer-Verlag
CY - Berlin Heidelberg
SN - 9783642387708
KW - piecewise testable languages
KW - acyclic automata
KW - locally con- fluent automata
N2 - 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.
ER -
KLÍMA, Ondřej and Libor POLÁK. Alternative Automata Characterization of Piecewise Testable Languages. In Marie-Pierre Béal, Olivier Carton. \textit{Developments in Language Theory}. Berlin Heidelberg: Springer-Verlag, 2013, p.~289-300. ISBN~978-3-642-38770-8. Available from: https://dx.doi.org/10.1007/978-3-642-38771-5\_{}26.
|
