J 2011

Complexity in Union-Free Regular Languages

JIRÁSKOVÁ, Galina a Tomáš MASOPUST

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

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í

Odkazy

Impakt faktor

Impact factor: 0.379

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

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ěněno: 26. 1. 2012 09:00, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

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