2013
Alternative Automata Characterization of Piecewise Testable Languages
KLÍMA, Ondřej a Libor POLÁKZákladní údaje
Originální název
Alternative Automata Characterization of Piecewise Testable Languages
Autoři
KLÍMA, Ondřej (203 Česká republika, garant, domácí) a Libor POLÁK (203 Česká republika, domácí)
Vydání
Berlin Heidelberg, Developments in Language Theory, od s. 289-300, 12 s. 2013
Nakladatel
Springer-Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Německo
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/13:00066861
Organizační jednotka
Přírodovědecká fakulta
ISBN
978-3-642-38770-8
ISSN
Klíčová slova anglicky
piecewise testable languages; acyclic automata; locally con- fluent automata
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 5. 3. 2014 14:46, doc. Mgr. Ondřej Klíma, Ph.D.
Anotace
V originále
We present a transparent condition on a minimal automaton which is equivalent to piecewise testability of the corresponding regular language. The condition simplifies the original Simon’s condition on the minimal automaton in a different way than conditions of Stern and Trahtman. Secondly, we prove that every piecewise testable language L is k-piecewise testable for k equal to the depth of the minimal DFA of L. This result improves all previously known estimates of such k.
Návaznosti
| GBP202/12/G061, projekt VaV |
|