Konferenzpaper

Herausgeberliste: Ito, M; Toyama, M

Jahr der Veröffentlichung: 2003

Seiten: 162-172

Zeitschrift: Lecture notes in computer science

Bandnummer: 2450

ISSN: 0302-9743

ISBN: 3-540-40431-7

Konferenz: 6th International Conference on Developments in Language Theory (DLT 2002)

Verlag: Springer

Serientitel: LECTURE NOTES IN COMPUTER SCIENCE

Abstract: 
We investigate the costs, in terms of states, of operations on infinite and finite unary regular languages where the languages are represented by nondeterministic finite automata. In particular, we consider Boolean operations, concatenation, iteration, and lambda-free iteration. Most of the bounds are tight in the exact number of states, i.e. the number is sufficient and necessary in the worst case. For the complementation of infinite languages a tight bound in the order of magnitude is shown.

Harvard-Zitierstil: Holzer, M. and Kutrib, M. (2003) Unary language operations and their nondeterministic state complexity, Lecture notes in computer science (Schriftenreihe), 2450, pp. 162-172

APA-Zitierstil: Holzer, M., & Kutrib, M. (2003). Unary language operations and their nondeterministic state complexity. Lecture notes in computer science (Schriftenreihe). 2450, 162-172.