Journalartikel
Autorenliste: Holzer, Markus; Kutrib, Martin; Meckel, Katja
Jahr der Veröffentlichung: 2012
Seiten: 68-80
Zeitschrift: Theoretical Computer Science
Bandnummer: 450
ISSN: 0304-3975
eISSN: 1879-2294
Open Access Status: Bronze
DOI Link: https://doi.org/10.1016/j.tcs.2012.04.028
Verlag: 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.
Zitierstile
Harvard-Zitierstil: 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-Zitierstil: 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
Schlagwörter
DESCRIPTIONAL COMPLEXITY; EVENTS; FINITE AUTOMATA; Nondeterministic finite automata; Operational state complexity; OPERATIONS; REGULAR LANGUAGES; Star-free languages
