Conference paper

Editor list: Ito, M; Toyama, M

Publication year: 2003

Pages: 162-172

Journal: Lecture notes in computer science

Volume number: 2450

ISSN: 0302-9743

ISBN: 3-540-40431-7

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

Publisher: Springer

Title of series: 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 Citation style: 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 Citation style: Holzer, M., & Kutrib, M. (2003). Unary language operations and their nondeterministic state complexity. Lecture notes in computer science (Schriftenreihe). 2450, 162-172.