Affiliations: Intelligence and Interaction Research Center, Korea
Institute of Science and Technology, P.O.BOX 131, Cheongryang, Seoul, Korea.
emmous@kist.re.kr | School of Computing, Queen's University,
Kingston, Ontario K7L 3N6, Canada. ksalomaa@cs.queensu.ca | Department of Computer Science, The Hong Kong
University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong SAR.
dwood@cs.ust.hk
Note: [] Address for correspondence: Intelligence and Interaction
Research Center, Korea Institute of Science and Technology, P.O.BOX 131,
Cheongryang, Seoul, Korea
Abstract: We investigate the nondeterministic state complexity of basic
operations for prefix-free regular languages. The nondeterministic state
complexity of an operation is the number of states that are necessary and
sufficient in the worst-case for a minimal nondeterministic finite-state
automaton that accepts the language obtained from the operation. We establish
the precise state complexity of catenation, union, intersection, Kleene star,
reversal and complementation for prefix-free regular languages.
Keywords: prefix-freeness, regular languages, nondeterministic state complexity, descriptional complexity
