D
2013
Alternative Automata Characterization of Piecewise Testable Languages
KLÍMA, Ondřej a Libor POLÁK
Zá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
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
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
Klíčová slova anglicky
piecewise testable languages; acyclic automata; locally con- fluent automata
Příznaky
Mezinárodní význam, Recenzováno
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 | Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI) | Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky |
|
Zobrazeno: 14. 11. 2024 16:58