JIRÁSKOVÁ, Galina a Tomáš MASOPUST. Complexity in Union-Free Regular Languages. International Journal of Foundations of Computer Science. World Scientific, 2011, roč. 22, č. 7, s. 1639-1653. ISSN 0129-0541. Dostupné z: https://dx.doi.org/10.1142/S0129054111008933.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Complexity in Union-Free Regular Languages
Autoři JIRÁSKOVÁ, Galina a Tomáš MASOPUST.
Vydání International Journal of Foundations of Computer Science, World Scientific, 2011, 0129-0541.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor 10201 Computer sciences, information science, bioinformatics
Utajení není předmětem státního či obchodního tajemství
WWW URL
Impakt faktor Impact factor: 0.379
Organizační jednotka Fakulta informatiky
Doi http://dx.doi.org/10.1142/S0129054111008933
UT WoS 000297580200011
Klíčová slova anglicky Union-free regular language; finite automaton; one-cycle-free-path automaton; descriptional complexity; closure properties
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Tomáš Masopust, Ph.D., DSc., učo 4030. Změněno: 26. 1. 2012 09:00.
Anotace
We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages accepted by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case.
VytisknoutZobrazeno: 2. 6. 2024 21:34