Abstract
We investigate the state complexity of the permutation operation over finite binary languages. We first give an upper bound of the state complexity of the permutation operation for a restricted case of these languages. We later present a general upper bound of the state complexity of permutation over finite binary languages, which is asymptotically the same as the previous case. Moreover, we show that there is a family of languages that the minimal DFA recognizing each of these languages needs at least as many states as the given upper bound for the restricted case. Furthermore, we investigate the state complexity of permutation by focusing on the structure of the minimal DFA.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Câmpeanu, C., Culik, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 60–70. Springer, Heidelberg (2001)
Domaratzki, M.: State complexity of proportional removals. J. Autom. Lang. Comb. 7(4), 455–468 (2002)
Ellul, K., Krawetz, B., Shallit, J., Wang, M.: Regular expressions: new results and open problems. J. Autom. Lang. Comb. 10(4), 407–437 (2005)
Gao, Y., Moreira, N., Reis, R., Yu, S.: A review of state complexity of individual operations. Technical report, Universidade do Porto, Technical Report Series DCC-2011-08, Version 1.1, September (2012). www.dcc.fc.up.pt/Pubs (To appear in Computer Science Review, 2015)
Goč, D., Palioudakis, A., Salomaa, K.: Nondeterministic state complexity of proportional removals. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 102–111. Springer, Heidelberg (2013)
Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. UCS 8(2), 193–234 (2002)
Han, Y.S., Salomaa, K.: State complexity of union and intersection of finite languages. Int. J. Found. Comput. Sci. 19(03), 581–595 (2008)
Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 148–157. Springer, Heidelberg (2003)
Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata – a survey. Inf. Comput. 209(3), 456–470 (2011)
Kleene, S.C.: Representation of events in nerve nets and finite automata. Technical report, DTIC Document (1951)
Lavado, G.J., Pighizzini, G., Seki, S.: Operational state complexity under Parikh equivalence. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 294–305. Springer, Heidelberg (2014)
Lupanov, O.: A comparison of two types of finite sources. Problemy Kibernetiki 9, 328–335 (1963)
Maslov, A.: Estimates of the number of states of finite automata. In: Soviet Mathematics Doklady, Translation from Doklady Akademii Nauk SSSR 194, vol. 11, pp. 1266–1268, 1373–1375 (1970)
McCulloch, W.S., Pitts, W.: A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys. 5(4), 115–133 (1943)
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT (FOCS), pp. 188–191. IEEE Computer Society (1971)
Moore, F.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. C–20(10), 1211–1214 (1971)
Parikh, R.J.: On context-free languages. J. ACM (JACM) 13(4), 570–581 (1966)
Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114–125 (1959)
Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2008)
Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315–328 (1994)
Yu, S.: Handbook of Formal Languages, Volume 1, Chap. Regular Languages, pp. 41–110. Springer, Heidelberg (1998)
Acknowledgment
This research was supported by the Basic Science Research Program through NRF funded by MEST (2012R1A1A2044562), the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512) and the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Palioudakis, A., Cho, DJ., Goč, D., Han, YS., Ko, SK., Salomaa, K. (2015). The State Complexity of Permutations on Finite Languages over Binary Alphabets. In: Shallit, J., Okhotin, A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Lecture Notes in Computer Science(), vol 9118. Springer, Cham. https://doi.org/10.1007/978-3-319-19225-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-19225-3_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19224-6
Online ISBN: 978-3-319-19225-3
eBook Packages: Computer ScienceComputer Science (R0)