Commutative regular languages – properties and state complexity. (English) Zbl 1434.68258
Ćirić, Miroslav (ed.) et al., Algebraic informatics. 8th international conference, CAI 2019, Niš, Serbia, June 30 – July 4, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11545, 151-163 (2019).
Summary: We consider the state complexity of intersection, union and the shuffle operation on commutative regular languages for arbitrary alphabets. Certain invariants will be introduced which generalize known notions from unary languages used for refined state complexity statements and existing notions for commutative languages used for the subclass of periodic languages. Our bound for shuffle is formulated in terms of these invariants and shown to be optimal, from this we derive the bound of \((2nm)^{|\varSigma|}\) for commutative languages of state complexities \(n\) and \(m\) respectively. This result is a considerable improvement over the general bound \(2^{mn-1}+2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-1)\).
We have no improvement for union and intersection for any alphabet, as was to be expected from the unary case. The general bounds are optimal here. Seeing commutative languages as generalizing unary languages is a guiding theme. For our results we take a closer look at a canonical automaton model for commutative languages.
For the entire collection see [Zbl 1428.68013].
We have no improvement for union and intersection for any alphabet, as was to be expected from the unary case. The general bounds are optimal here. Seeing commutative languages as generalizing unary languages is a guiding theme. For our results we take a closer look at a canonical automaton model for commutative languages.
For the entire collection see [Zbl 1428.68013].
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Brzozowski, J.; Jirásková, G.; Liu, B.; Rajasekaran, A.; Szykuła, M.; Câmpeanu, C.; Manea, F.; Shallit, J., On the state complexity of the shuffle of regular languages, Descriptional Complexity of Formal Systems, 73-86, 2016, Cham: Springer, Cham · Zbl 1476.68127 · doi:10.1007/978-3-319-41114-9_6 |
| [2] | Brzozowski, JA; Liu, B., Quotient complexity of star-free languages, Int. J. Found. Comput. Sci., 23, 6, 1261-1276, 2012 · Zbl 1272.68206 · doi:10.1142/S0129054112400515 |
| [3] | Brzozowski, JA; Simon, I., Characterizations of locally testable events, Discrete Math., 4, 3, 243-271, 1973 · Zbl 0255.94032 · doi:10.1016/S0012-365X(73)80005-6 |
| [4] | Ehrenfeucht, A.; Haussler, D.; Rozenberg, G., On regularity of context-free languages, Theor. Comput. Sci., 27, 311-332, 1983 · Zbl 0553.68044 · doi:10.1016/0304-3975(82)90124-4 |
| [5] | Gao, Y.; Moreira, N.; Reis, R.; Yu, S., A survey on operational state complexity, J. Autom. Lang. Comb., 21, 4, 251-310, 2017 · Zbl 1380.68253 |
| [6] | Ginsburg, S.; Spanier, EH, Bounded regular sets, Proc. Am. Math. Soc., 17, 1043-1049, 1966 · Zbl 0147.25301 · doi:10.1090/S0002-9939-1966-0201310-3 |
| [7] | Cano Gómez, A.; Álvarez, GI; Clark, A.; Coste, F.; Miclet, L., Learning commutative regular languages, Grammatical Inference: Algorithms and Applications, 71-83, 2008, Heidelberg: Springer, Heidelberg · Zbl 1177.68107 · doi:10.1007/978-3-540-88009-7_6 |
| [8] | Jirásková, G.; Masopust, T.; Holzer, M.; Kutrib, M.; Pighizzini, G., State complexity of projected languages, Descriptional Complexity of Formal Systems, 198-211, 2011, Heidelberg: Springer, Heidelberg · Zbl 1341.68096 · doi:10.1007/978-3-642-22600-7_16 |
| [9] | Maslov, AN, Estimates of the number of states of finite automata, Dokl. Akad. Nauk SSSR, 194, 6, 1266-1268, 1970 · Zbl 0222.94064 |
| [10] | McNaughton, R., The loop complexity of pure-group events, Inf. Control, 11, 1-2, 167-176, 1967 · Zbl 0166.26905 · doi:10.1016/S0019-9958(67)90481-0 |
| [11] | McNaughton, R.; Papert, SA, Counter-Free Automata, 1971, Cambridge: The MIT Press, Cambridge · Zbl 0232.94024 |
| [12] | Pighizzini, G.; Yu, S.; Păun, A., Unary language concatenation and its state complexity, Implementation and Application of Automata, 252-262, 2001, Heidelberg: Springer, Heidelberg · Zbl 0989.68081 · doi:10.1007/3-540-44674-5_21 |
| [13] | Pighizzini, G.; Shallit, J., Unary language operations, state complexity and Jacobsthal’s function, Int. J. Found. Comput. Sci., 13, 1, 145-159, 2002 · Zbl 1066.68072 · doi:10.1142/S012905410200100X |
| [14] | Yu, S.; Zhuang, Q.; Salomaa, K., The state complexities of some basic operations on regular languages, Theor. Comput. Sci., 125, 2, 315-328, 1994 · Zbl 0795.68112 · doi:10.1016/0304-3975(92)00011-F |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
