2012
Biautomata for k-Piecewise Testable Languages
KLÍMA, Ondřej a Libor POLÁKZákladní údaje
Originální název
Biautomata for k-Piecewise Testable Languages
Název česky
Biautomaty pro po částech testovaltelné jazyky stupně k
Autoři
KLÍMA, Ondřej a Libor POLÁK
Vydání
Berlin Heidelberg, Developments in Language Theory, od s. 344-355, 12 s. 2012
Nakladatel
Springer - Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Švýcarsko
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14310/12:00057569
Organizační jednotka
Přírodovědecká fakulta
ISBN
978-3-642-31652-4
ISSN
UT WoS
000440210900031
EID Scopus
2-s2.0-84864984744
Klíčová slova česky
biautomata; piecewise testable languages
Klíčová slova anglicky
biautomaty; po částech testovatelné jazyky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 10. 7. 2020 10:26, Mgr. Marie Novosadová Šípková, DiS.
Anotace
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.
Návaznosti
| GBP202/12/G061, projekt VaV |
|