×
Brzozowski, Janusz; Jirásková, Galina; Zou, Chenglong

Quotient complexity of closed languages. (English) Zbl 1380.68249

Theory Comput. Syst. 54, No. 2, 277-292 (2014).
Summary: A language \(L\) is prefix-closed if, whenever a word \(w\) is in \(L\), then every prefix of \(w\) is also in \(L\). We define suffix-, factor-, and subword-closed languages in an analogous way, where by factor we mean contiguous subsequence, and by subword we mean scattered subsequence. We study the state complexity (which we prefer to call quotient complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated applications of positive closure and complement to a closed language result in at most four distinct languages, while Kleene closure and complement give at most eight.

Cited in 13 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

closed language; finite automaton; quotient complexity; regular language; state complexity
PDF BibTeX XML Cite
\textit{J. Brzozowski} et al., Theory Comput. Syst. 54, No. 2, 277--292 (2014; Zbl 1380.68249)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] Ang, T.; Brzozowski, J., Languages convex with respect to binary relations, and their closure properties, Acta Cybern., 19, 445-464, (2009) · Zbl 1199.68168
[2] Avgustinovich, S.V.; Frid, A.E., A unique decomposition theorem for factorial languages, Int. J. Algebra Comput., 15, 149-160, (2005) · Zbl 1102.68052
[3] Bassino, F.; Giambruno, L.; Nicaud, C.; López-Ortiz, A. (ed.), Complexity of operations on cofinite languages, No. 6034, 222-233, (2010), Berlin · Zbl 1283.68188
[4] Brzozowski, J., Derivatives of regular expressions, J. ACM, 11, 481-494, (1964) · Zbl 0225.94044
[5] Brzozowski, J.; Dediu, A.H. (ed.); Fernau, H. (ed.); Martin-Vide, C. (ed.), Complexity in convex languages, No. 6031, 1-15, (2010), Berlin · Zbl 1284.68341
[6] Brzozowski, J., Quotient complexity of regular languages, J. Autom. Lang. Comb., 15, 71-89, (2010) · Zbl 1345.68200
[7] Brzozowski, J.; Grant, E.; Shallit, J., Closures in formal languages and kuratowski’s theorem, Int. J. Found. Comput. Sci., 22, 301-321, (2011) · Zbl 1246.68139
[8] Brzozowski, J.; Jirásková, G.; Li, B., Quotient complexity of ideal languages, Theor. Comput. Sci., 470, 36-52, (2013) · Zbl 1283.68190
[9] Brzozowski, J.; Jirásková, G.; Li, B.; Smith, J.; Dömösi, P. (ed.); Szabolcs, I. (ed.), Quotient complexity of bifix-, factor-, and subword-free languages, 123-137, (2011), Nyíregyháza · Zbl 1341.68079
[10] Brzozowski, J.; Santean, N., Predictable semiautomata, Theor. Comput. Sci., 410, 3236-3249, (2009) · Zbl 1193.68151
[11] Brzozowski, J.; Shallit, J.; Xu, Z., Decision problems for convex languages, Inf. Comput., 209, 353-367, (2011) · Zbl 1217.68125
[12] Câmpeanu, C.; Culik, K.; Salomaa, K.; Yu, S.; Boldt, O. (ed.); Jürgensen, H. (ed.), State complexity of basic operations on finite languages, No. 2214, 60-70, (2001), Berlin · Zbl 1050.68091
[13] Luca, A.; Varricchio, S.; Capocelli, R. (ed.), Some combinatorial properties of factorial languages, 258-266, (1990), Berlin · Zbl 0797.68131
[14] Galil, Z.; Simon, J., A note on multiple-entry finite automata, J. Comput. Syst. Sci., 12, 350-351, (1976) · Zbl 0329.94023
[15] Gill, A.; Kou, L.T., Multiple-entry finite automata, J. Comput. Syst. Sci., 9, 1-19, (1974) · Zbl 0285.94030
[16] Gruber, H.; Holzer, M.; Kutrib, M., The size of higman-haines sets, Theor. Comput. Sci., 387, 167-176, (2007) · Zbl 1143.68035
[17] Gruber, H.; Holzer, M.; Kutrib, M., More on the size of higman-haines sets: effective constructions, Fundam. Inform., 91, 105-121, (2009) · Zbl 1192.68410
[18] Haines, L.H., On free monoids partially ordered by embedding, J. Comb. Theory, 6, 94-98, (1969) · Zbl 0224.20065
[19] Han, Y.S.; Salomaa, K., State complexity of basic operations on suffix-free regular languages, Theor. Comput. Sci., 410, 2537-2548, (2009) · Zbl 1172.68033
[20] Han, Y.S.; Salomaa, K.; Wood, D.; Ésik, Z. (ed.); Fülöp, Z. (ed.), Operational state complexity of prefix-free regular languages, 99-115, (2009), Szeged · Zbl 1182.68105
[21] Holzer, M.; Salomaa, K.; Yu, S., On the state complexity of \(k\)-entry deterministic finite automata, J. Autom. Lang. Comb., 6, 453-466, (2001) · Zbl 1050.68093
[22] Jirásek, J.; Jirásková, G.; Szabari, A., State complexity of concatenation and complementation, Int. J. Found. Comput. Sci., 16, 511-529, (2005) · Zbl 1097.68062
[23] Kao, J.Y.; Rampersad, N.; Shallit, J., On NFAs where all states are final, initial, or both, Theor. Comput. Sci., 410, 5010-5021, (2009) · Zbl 1194.68140
[24] Kuratowski, C.: Sur l’opération \(\overline{A}\) de l’analysis situs. Fundam. Math. 3, 182-199 (1922) (in French) · JFM 48.0210.04
[25] Maslov, A.N., Estimates of the number of states of finite automata, Dokl. Akad. Nauk SSSR, 194, 1266-1268, (1970)
[26] Mirkin, B.G., On dual automata, Kibernetika, 2, 7-10, (1966)
[27] Okhotin, A., On the state complexity of scattered substrings and superstrings, Fundam. Inform., 99, 325-338, (2010) · Zbl 1208.68139
[28] Pighizzini, G.; Shallit, J., Unary language operations, state complexity and jacobsthal’s function, Int. J. Found. Comput. Sci., 13, 145-159, (2002) · Zbl 1066.68072
[29] Thierrin, G.; Nivat, M. (ed.), Convex languages, 481-492, (1973), Amsterdam
[30] Veloso, P.A.S.; Gill, A., Some remarks on multiple-entry finite automata, J. Comput. Syst. Sci., 18, 304-306, (1979) · Zbl 0402.68046
[31] Yu, S., State complexity of regular languages, J. Autom. Lang. Comb., 6, 221-234, (2001) · Zbl 0978.68087
[32] Yu, S.; Zhuang, Q.; Salomaa, K., The state complexities of some basic operations on regular languages, Theor. Comput. Sci., 125, 315-328, (1994) · Zbl 0795.68112
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.