Number of the records: 1

Complexity in Union-Free Regular Languages

SYSNO ASEP	0346729
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	Complexity in Union-Free Regular Languages
Author(s)	Jirásková, G. (SK) Masopust, Tomáš (MU-W)_{RID, ORCID, SAI}
Source Title	Developments in Language Theory. - Berlin : Springer, 2010 / Gao Y. ; Lu H. ; Seki S. - ISBN 978-3-642-14455-4
Pages	s. 255-266
Number of pages	12 s.
Action	DLT2010. 14th International Conference on Developments in Language Theory
Event date	17.08.2010-20.08.2010
VEvent location	London
Country	CA - Canada
Event type	WRD
Language	eng - English
Country	DE - Germany
Keywords	descriptional complexity ; union-free regular language ; one-cycle-free-path finite automaton
Subject RIV	BA - General Mathematics
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000286402700024
EID SCOPUS	78049312270
DOI	10.1007/978-3-642-14455-4_24
Annotation	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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2011

Number of the records: 1