Complexity in Union-Free Regular Languages

JIRÁSKOVÁ, Galina a Tomáš MASOPUST. Complexity in Union-Free Regular Languages. In DLT 2010, LNCS 6224. London, ON, Canada: Springer-Verlag Berlin Heidelberg, 2010, s. 255-266. ISBN 978-3-642-14454-7.

Základní údaje

Originální název

Complexity in Union-Free Regular Languages

Autoři

JIRÁSKOVÁ, Galina a Tomáš MASOPUST

Vydání

London, ON, Canada, DLT 2010, LNCS 6224, od s. 255-266, 2010

Nakladatel

Springer-Verlag Berlin Heidelberg

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-14454-7

ISSN

UT WoS

000286402700024

Klíčová slova anglicky

Descriptional complexity, union-free regular language, one-cycle-free-path finite automaton.

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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 recognized 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.