Další formáty:
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 a 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, s.~289-300. ISBN~978-3-642-38770-8. Dostupné z: https://dx.doi.org/10.1007/978-3-642-38771-5\_{}26.
|