On the State Complexity of Scattered Substrings and Superstrings

• Autorzy: Okhotin A.
• Języki publikacji: EN

Abstrakty

EN

It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least [formula] states (the known upper bound is 2*n), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least [formula] states. A similar state complexity function for scattered superstrings is determined to be exactly 2*(n-2) + 1 for an alphabet of at least n -2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least [formula]

Słowa kluczowe

EN

descriptional complexity; finite automata; state complexity; substring; subword; subsequence; Higman–Haines sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 3
• Strony: 325--338
• Opis fizyczny: Bibliogr. 16 poz., wykr.

Twórcy

autor

Okhotin A.

• Department of Mathematics, University of Turku, Turku FIN–20014, Finland,

Bibliografia

• [1] J.-C. Birget, "Intersection and union of regular languages and state complexity", Information Processing Letters, 43 (1992), 185-190.
• [2] C. Câmpeanu, K. Salomaa, S. Yu, "Tight lower bound for the state complexity of shuffle of regular languages", Journal of Automata, Languages and Combinatorics, 7 (2002), 303-310.
• [3] H. Gruber, M. Holzer, M. Kutrib, "The size of Higman-Haines sets", Theoretical Computer Science, 387:2 (2007), 167-176.
• [4] H. Gruber, M. Holzer, M. Kutrib, "More on the size of Higman-Haines sets: effective constructions", Fundamenta Informaticae, 91:1 (2009), 105-121.
• [5] L. H. Haines, "On freemonoids partially ordered by embedding", Journal of Combinatorial Theory, 6 (1969), 94-98.
• [6] G. Higman, "Ordering by divisibility in abstract algebras", The strange volume number is from the publisher. Proceedings of London Mathematical Society, s3-2:1 (1952), 326-336.
• [7] G. Jirásková, "State complexity of some operations on binary regular languages", Theoretical Computer Science, 330 (2005), 287-298.
• [8] G. Jirásková, A. Okhotin, "State complexity of cyclic shift", RAIRO Informatique Théorique et Applications, 42:2 (2008), 335-360.
• [9] J. van Leeuven, "Effective construction in well-partially-ordered free monoids", Discrete Mathematics, 21:3 (1978), 237-252.
• [10] A. N.Maslov, "Estimates of the number of states of finite automata", Soviet Mathematics Doklady, 11 (1970), 1373-1375.
• [11] N. Rampersad, "The state complexity of L2 and Lk", Information Processing Letters, 98 (2006), 231-234.
• [12] A. Salomaa, K. Salomaa, S. Yu, "State complexity of combined operations", Theoretical Computer Science, 383:2-3 (2007), 140-152.
• [13] A. Salomaa, D. Wood, S. Yu, "On the state complexity of reversals of regular languages", Theoretical Computer Science, 320 (2004), 315-329.
• [14] J. Shallit, "New directions in state complexity", a talk presented at the DCFS 2006 workshop (Las Cruces, New Mexico, USA, June 21-23, 2006).
• [15] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999.
• [16] S. Yu, Q. Zhuang, K. Salomaa, "The state complexity of some basic operations on regular languages", Theoretical Computer Science, 125 (1994), 315-328.