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.
|
