KLÍMA, Ondřej a Libor POLÁK. Alternative Automata Characterization of Piecewise Testable Languages. In Marie-Pierre Béal, Olivier Carton. Developments in Language Theory. Berlin Heidelberg: Springer-Verlag, 2013. s. 289-300, 12 s. ISBN 978-3-642-38770-8. doi:10.1007/978-3-642-38771-5_26.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 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 0302-9743
Doi http://dx.doi.org/10.1007/978-3-642-38771-5_26
Klíčová slova anglicky piecewise testable languages; acyclic automata; locally con- fluent automata
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Změněno: 5. 3. 2014 14:46.
Anotace
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 VaVNázev: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Projekty na podporu excelence v základním výzkumu
VytisknoutZobrazeno: 18. 8. 2019 05:01