Other formats:
BibTeX
LaTeX
RIS
@inproceedings{991109, 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-31653-1_31}, editor = {Hsu-Chun Yen, Oscar H. Ibarra}, keywords = {biautomaty; po částech testovatelné jazyky}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Berlin Heidelberg}, isbn = {978-3-642-31652-4}, pages = {344-355}, publisher = {Springer - Verlag}, title = {Biautomata for k-Piecewise Testable Languages}, year = {2012} }
TY - JOUR ID - 991109 AU - Klíma, Ondřej - Polák, Libor PY - 2012 TI - Biautomata for k-Piecewise Testable Languages PB - Springer - Verlag CY - Berlin Heidelberg SN - 9783642316524 KW - biautomaty KW - po částech testovatelné jazyky N2 - An effective characterization of piecewise testable languages was given by Simon in 1972. A difficult part of the proof is to show that if L has a J -trivial syntactic monoid M(L) then L is k-piecewise testable for a suitable k. By Simon’s original proof, an appropriate k could be taken as two times the maximal length of a chain of ideals in M(L) . In this paper we improve this estimate of k using the concept of biautomaton: a kind of finite automaton which arbitrarily alternates between reading the input word from the left and from the right. We prove that an appropriate k could be taken as the length of the longest simple path in the canonical biautomaton of L. We also show that this bound is better than the known bounds which use the syntactic monoid of L. ER -
KLÍMA, Ondřej and Libor POLÁK. Biautomata for k-Piecewise Testable Languages. In Hsu-Chun Yen, Oscar H. Ibarra. \textit{Developments in Language Theory}. Berlin Heidelberg: Springer - Verlag, 2012, p.~344-355. ISBN~978-3-642-31652-4. Available from: https://dx.doi.org/10.1007/978-3-642-31653-1\_{}31.
|