Abstract
We continue our research on the descriptional complexity of chop operations. Informally, the chop of two words is like their concatenation with the touching letters merged if they are equal, otherwise their chop is undefined. The iterated variants chop-star and chop-plus are defined similar as the classical operations Kleene star and plus. We investigate the state complexity of chop operations on unary and/or finite languages, and obtain similar bounds as for the classical operations.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Babu, S.A., Pandya, P.K.: Chop expressions and discrete duration calculus. In: Modern Applications of Automata Theory. IISc research Monographs Series, vol. 2. World Scientific (2010)
Birget, J.C.: Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43, 185–190 (1992)
Câmpeanu, C., Culik II, 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)
Cărăuşu, A., Păun, G.: String intersection and short concatenation. Rev. Roumaine Math. Pures Appl. 26, 713–726 (1981)
Domaratzki, M.: Minimality in Template-Guided Recombination. Inform. Comput. 270, 1209–1220 (2009)
Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59, 75–77 (1996)
Holzer, M., Jakobi, S.: Chop Operations and Expressions: Descriptional Complexity Considerations. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 264–275. Springer, Heidelberg (2011)
Holzer, M., Jakobi, S., Kutrib, M.: The chop of languages. In: Automata and Formal Languages (AFL), Debrecen, Hungary, pp. 197–210 (2011)
Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Internat. J. Found. Comput. Sci. 14(6), 1087–1102 (2003)
Ito, M., Lischke, G.: Generalized periodicity and primitivity. Math. Logic Q. 53, 91–106 (2007)
Leiss, E.: Succinct representation of regular languages by Boolean automata. Theoret. Comput. Sci. 13, 323–330 (1981)
Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Dokl. 11, 1373–1375 (1970)
Mateescu, A., Salomaa, A.: Parallel composition of words with re-entrant symbols. Analele Universitǎţii Bucureşti Matematicǎ-Informaticǎ 45, 71–80 (1996)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114–125 (1959)
Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315–328 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Holzer, M., Jakobi, S. (2012). State Complexity of Chop Operations on Unary and Finite Languages. In: Kutrib, M., Moreira, N., Reis, R. (eds) Descriptional Complexity of Formal Systems. DCFS 2012. Lecture Notes in Computer Science, vol 7386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31623-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-31623-4_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31622-7
Online ISBN: 978-3-642-31623-4
eBook Packages: Computer ScienceComputer Science (R0)