Biautomata for k-Piecewise Testable Languages

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KLÍMA Ondřej POLÁK Libor

Year of publication 2012
Type Article in Proceedings
Conference Developments in Language Theory
MU Faculty or unit

Faculty of Science

Citation
Doi http://dx.doi.org/10.1007/978-3-642-31653-1_31
Field General mathematics
Keywords biautomaty; po částech testovatelné jazyky
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.