No Access

Further Remarks on the Operational Nonterminal Complexity

Jürgen Dassow

Jürgen Dassow

Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, PSF 4120, 39016 Magdeburg, Germany

E-mail Address: dassow@iws.cs.uni-magdeburg.de

Search for more papers by this author

https://doi.org/10.1142/S0129054121410021Cited by:1 (Source: Crossref)

This article is part of the issue:

Special Issue: Dedicated to Nelma Moreira and Rogério Reis on the Occasion of Their 60th Birthdays

Abstract

For a regular language $L$ , let $Var (L)$ be the minimal number of nonterminals necessary to generate $L$ by right linear grammars. Moreover, for natural numbers $k_{1}, k_{2}, \dots, k_{n}$ and an $n$ -ary regularity preserving operation $f$ , let the range $g_{f}^{Var} (k_{1}, k_{2}, \dots, k_{n})$ be the set of all numbers $k$ such that there are regular languages $L_{1}, L_{2}, \dots, L_{n}$ with $Var (L_{i}) = k_{i}$ for $1 \leq i \leq n$ and $Var (f (L_{1}, L_{2}, \dots, L_{n})) = k$ . We show that, for the circular shift operation $Circ$ , $g_{Circ}^{Var} (n)$ is infinite for all $n$ , and we completely determine the set $g_{Circ}^{Var} (2)$ . Moreover, we give a precise range for the left right quotient and a partial result for the left quotient. Furthermore, we add some values to the range for the operation intersection which improves the result of [2].

Communicated by Martin Kutrib

Keywords:

References

1. J. Dassow, On the number of accepting states of finite automata, J. Autom. Lang. Comb. 21 (2016) 55–67. Google Scholar
2. J. Dassow, Operational complexity and right linear grammars, Acta Informatica, to appear. Web of Science, Google Scholar
3. J. Dassow and R. Harbich, Descriptional complexity of union and star on context-free languages, J. Autom. Lang. Comb. 17 (2012) 123–143. Google Scholar
4. K. Ellul, B. Krawetz, J. Shallit and M.-W. Wang, Regular expressions: New results and open problems, J. Autom. Lang. Comb. 10 (2005) 407–437. Google Scholar
5. Y. Gao, N. Moreira, R. Reis and S. Yu, A survey on operational state complexity, J. Autom. Lang. Comb. 21 (2016) 251–310. Google Scholar
6. Y. Gao, K. Salomaa and S. Yu, Transition complexity of incomplete dfas, Fundamenta Informaticae 110 (2011) 143–158. Crossref, Web of Science, Google Scholar
7. H. Gruber and M. Holzer, Language operations with regular expressions of polynomial size, Theoret. Comput. Sci. 418 (2009) 3281–3289. Crossref, Web of Science, Google Scholar
8. R. Harbich, Regel- und Symbolkomplexität kontextfreier Sprachen unter ausgewählten Operationen, PhD thesis (2019). Google Scholar
9. M. Holzer and M. Kutrib, State complexity of basic operations on nondeterministic automata, Implementation and Application of Automata, eds. J.-M. Champernaud and D. Maurel, LNCS, Vol. 2608 (Springer-Verlag, Berlin, 2003), pp. 148–157. Crossref, Google Scholar
10. M. Holzer and M. Kutrib, Nondeterministic finite automata — recent results on the descriptional and computational complexity, Int. J. Found. Comput. Sci. 20 (2009) 563–580. Link, Web of Science, Google Scholar
11. M. Hospodár and M. Holzer, The ranges of accepting state complexities of languages resulting from some operations, Implementation and Application of Automata, ed. C. Câmpeanu, LNCS, Vol. 10977 (Springer-Verlag, Berlin, 2018), pp. 198–210. Crossref, Google Scholar
12. M. Hricko, G. Jirásková and A. Szabari, Union and intersection of regular languages and descriptional complexity, Proc. 7th Int. Workshop of Descriptional Complexity of Formal Systems, eds. C. Mereghetti, B. Palano, G. Pighizzini and D. Wotschke (University of Milano, 2005), pp. 170–181. Google Scholar
13. G. Jirásková, Concatenation of regular languages and descriptional complexity, 4th Int. Computer Science Symposium in Russia 2009, eds. A. E. Frid, A. Morozov, A. Rybalchenko and K.-W. Wagner, LNCS, Vol. 5675 (Springer-Verlag, Berlin, 2009), pp. 203–214. Crossref, Google Scholar
14. G. Jirásková, The ranges of state complexities for complement, star, and reversal of regular languages, Int. J. Found. Comput. Sci. 25 (2014) 101–124. Link, Web of Science, Google Scholar
15. G. Jirásková and A. Okhotin, State complexity of cyclic shift, RAIRO — Theoret. Inform. Appl. 42 (2008) 335–360. Crossref, Web of Science, Google Scholar
16. E. Maia, N. Moreira and R. Reis, Incomplete operational transition complexity of regular languages, Inform. Comput. 244 (2015) 1–22. Crossref, Web of Science, Google Scholar
17. S. Yu, Q. Zhuang and K. Salomaa, The state complexities of some basic operations on regular languages, Theoret. Comput. Sci. 125 (1994) 315–328. Crossref, Web of Science, Google Scholar