D
2012
Biautomata for k-Piecewise Testable Languages
KLÍMA, Ondřej and Libor POLÁK
Basic information
Original name
Biautomata for k-Piecewise Testable Languages
Name in Czech
Biautomaty pro po částech testovaltelné jazyky stupně k
Authors
KLÍMA, Ondřej (203 Czech Republic, guarantor, belonging to the institution) and Libor POLÁK (203 Czech Republic, belonging to the institution)
Edition
Berlin Heidelberg, Developments in Language Theory, p. 344-355, 12 pp. 2012
Publisher
Springer - Verlag
Other information
Type of outcome
Stať ve sborníku
Field of Study
10101 Pure mathematics
Country of publisher
Switzerland
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
Impact factor
Impact factor: 0.402 in 2005
RIV identification code
RIV/00216224:14310/12:00057569
Organization unit
Faculty of Science
Keywords (in Czech)
biautomata; piecewise testable languages
Keywords in English
biautomaty; po částech testovatelné jazyky
Tags
International impact, Reviewed
V originále
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.
Links
GBP202/12/G061, research and development project | Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI) | Investor: Czech Science Foundation |
|
Displayed: 14/11/2024 14:13