Journal article
Authors list: Holzer, Markus; Kutrib, Martin; Meckel, Katja
Publication year: 2012
Pages: 68-80
Journal: Theoretical Computer Science
Volume number: 450
ISSN: 0304-3975
eISSN: 1879-2294
Open access status: Bronze
DOI Link: https://doi.org/10.1016/j.tcs.2012.04.028
Publisher: Elsevier
Abstract:
We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. This nicely complements the results recently obtained by Brzozowski and Liu (2011) [8] for the operation problem of star-free and unary star-free languages accepted by deterministic finite automata. (C) 2012 Elsevier B.V. All rights reserved.
Citation Styles
Harvard Citation style: Holzer, M., Kutrib, M. and Meckel, K. (2012) Nondeterministic state complexity of star-free languages, Theoretical Computer Science, 450, pp. 68-80. https://doi.org/10.1016/j.tcs.2012.04.028
APA Citation style: Holzer, M., Kutrib, M., & Meckel, K. (2012). Nondeterministic state complexity of star-free languages. Theoretical Computer Science. 450, 68-80. https://doi.org/10.1016/j.tcs.2012.04.028
Keywords
DESCRIPTIONAL COMPLEXITY; EVENTS; FINITE AUTOMATA; Nondeterministic finite automata; Operational state complexity; OPERATIONS; REGULAR LANGUAGES; Star-free languages
