Operational complexity and right linear grammars
Author:
Open Access
- 19 July 2021
- journal article
- research article
- Published by Springer Nature in Acta Informatica
- Vol. 58 (4) , 281-299
Abstract
For a regular language L, let $${{\,\mathrm{Var}\,}}(L)$$ be the minimal number of nonterminals necessary to generate L by right linear grammars. Moreover, for natural numbers $$k_1,k_2,\ldots ,k_n$$ and an n-ary regularity preserving operation f, let $$g_f^{{{\,\mathrm{Var}\,}}}(k_1,k_2,\ldots ,k_n)$$ be the set of all numbers k such that there are regular languages $$L_1,L_2,\ldots , L_n$$ such that $${{\,\mathrm{Var}\,}}(L_i)=k_i$$ for $$1\le i\le n$$ and $${{\,\mathrm{Var}\,}}(f(L_1,L_2,\ldots , L_n))=k$$ . We completely determine the sets $$g_f^{{{\,\mathrm{Var}\,}}}$$ for the operations reversal, Kleene-closures $$+$$ and $$*$$ , and union; and we give partial results for product and intersection.
Keywords
Funding Information
- Otto-von-Guericke-Universität Magdeburg
This publication has 9 references indexed in Scilit:
- Incomplete operational transition complexity of regular languagesInformation and Computation, 2015
- THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGESInternational Journal of Foundations of Computer Science, 2014
- Transition Complexity of Incomplete DFAsFundamenta Informaticae, 2011
- Complexity in Prefix-Free Regular LanguagesElectronic Proceedings in Theoretical Computer Science, 2010
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITYInternational Journal of Foundations of Computer Science, 2009
- Language operations with regular expressions of polynomial sizeTheoretical Computer Science, 2009
- Quotient Complexity of Regular LanguagesElectronic Proceedings in Theoretical Computer Science, 2009
- Concatenation of Regular Languages and Descriptional ComplexityLecture Notes in Computer Science, 2009
- State Complexity of Basic Operations on Nondeterministic Finite Automata2003