Generic results for concatenation hierarchies. (English) Zbl 1423.68264
Summary: In the theory of formal languages, the understanding of concatenation hierarchies of regular languages is one of the most fundamental and challenging topics. In this paper, we survey progress made on this problem since 1971. We also establish new generic statements regarding this problem.
MSC:
| 68Q45 | Formal languages and automata |
| 68-02 | Research exposition (monographs, survey articles) pertaining to computer science |
| 68-03 | History of computer science |
Keywords:
concatenation hierarchies; regular languages; membership problem; separation problem; first-order logic; quantifier alternationReferences:
| [1] | Almeida, J.: Some algorithmic problems for Pseudovarieties. Publicationes Mathematicae Debrecen 54, 531-552 (1999). Proceedings of Automata and Formal Languages, VIII · Zbl 0981.20049 |
| [2] | Arfi, M.: Polynomial operations on rational languages. In: STACS’87, Lect. Notes Comp. Sci., pp. 198-206. Springer (1987) · Zbl 0635.68078 |
| [3] | Arfi, M.: Opérations polynomiales et hiérarchies de concaténation. Theoret. Comp. Sci. 91(1), 71-84 (1991) · Zbl 0751.68031 · doi:10.1016/0304-3975(91)90268-7 |
| [4] | Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata, volume 129 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2009) |
| [5] | Bojańczyk, M.: Star height via games. In: LICS’15, pp. 214-219. IEEE Computer Society (2015) · Zbl 1401.68148 |
| [6] | Branco, M., Pin, J.-É.: Equations defining the polynomial closure of a lattice of regular languages. In: ICALP 2009, volume 5556 of Lect. Notes Comp. Sci., pp. 115-126. Springer (2009) · Zbl 1248.68340 |
| [7] | Brzozowski, J.A.: Developments in the theory of regular languages. In: IFIP Congress, pp. 29-40 (1980) · Zbl 0443.68062 |
| [8] | Brzozowski, J.A.: Open problems about regular languages. In: Book, R.V. (ed.) Formal Language Theory, pp. 23-47. Academic Press (1980) |
| [9] | Brzozowski, J.A., Cohen, R.S.: Dot-depth of star-free events. J. Comput. Syst. Sci. 5(1), 1-16 (1971) · Zbl 0217.29602 · doi:10.1016/S0022-0000(71)80006-5 |
| [10] | Brzozowski, J.A., Knast, R.: The dot-depth hierarchy of star-free languages is infinite. J. Comput. Syst. Sci. 16(1), 37-55 (1978) · Zbl 0368.68074 · doi:10.1016/0022-0000(78)90049-1 |
| [11] | Colcombet, T.: Factorization forests for infinite words and applications to countable scattered linear orderings. Theor. Comput. Sci. 411(4-5), 751-764 (2010) · Zbl 1183.68336 · doi:10.1016/j.tcs.2009.10.013 |
| [12] | Dejean, F., Schützenberger, M.P.: On a question of Eggan. Inf. Control. 9(1), 23-25 (1966) · Zbl 0209.02903 · doi:10.1016/S0019-9958(66)90083-0 |
| [13] | Eggan, L.C.: Transition graphs and the star-height of regular events. Michigan Math. J. 10(4), 385-397 (1963) · Zbl 0173.01504 · doi:10.1307/mmj/1028998975 |
| [14] | Glaßer, C., Schmitz, H.: Languages of dot-depth 3/2. Theory Comput. Syst. 42(2), 256-286 (2007) · Zbl 1141.68037 · doi:10.1007/s00224-007-9002-0 |
| [15] | Hashiguchi, K.: Representation theorems on regular languages. J. Comput. Syst. Sci. 27(1), 101-115 (1983) · Zbl 0516.68063 · doi:10.1016/0022-0000(83)90031-4 |
| [16] | Hashiguchi, K.: Algorithms for determining relative star height and star height. Inf. Comput. 78(2), 124-169 (1988) · Zbl 0668.68081 · doi:10.1016/0890-5401(88)90033-8 |
| [17] | Kirsten, D.: Distance desert automata and the star height problem. RAIRO-Theor. Inf. Appl. 39(3), 455-509 (2005) · Zbl 1082.20041 · doi:10.1051/ita:2005027 |
| [18] | Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C., McCarthy, J. (eds.) Annals of Mathematics Studies 34, pp. 3-41. Princeton University Press (1956) · Zbl 0074.11204 |
| [19] | Knast, R.: A semigroup characterization of dot-depth one languages. RAIRO - Theor. Inform. Appl. 17(4), 321-330 (1983) · Zbl 0522.68063 · doi:10.1051/ita/1983170403211 |
| [20] | Kufleitner, M.: The height of factorization forests. In: Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS’08, pp. 443-454 (2008) · Zbl 1173.68567 |
| [21] | McNaughton, R., Papert, S.A.: Counter-Free Automata. MIT Press, Cambridge (1971) · Zbl 0232.94024 |
| [22] | Nerode, A.: Linear automaton transformations. Proc. Am. Math. Soc. 9(4), 541-544 (1958) · Zbl 0089.33403 · doi:10.1090/S0002-9939-1958-0135681-9 |
| [23] | Perrin, D., Pin, J.-É.: First-order logic and star-free sets. J. Comput. Syst. Sci. 32(3), 393-406 (1986) · Zbl 0618.03015 · doi:10.1016/0022-0000(86)90037-1 |
| [24] | Pin, J.-É.: A variety theorem without complementation. Russian mathem. (Iz. VUZ) 39, 74-83 (1995) |
| [25] | Pin, J.-É.: An explicit formula for the intersection of two polynomials of regular languages. In: DLT 2013, Volume 7907 of Lect. Notes Comp. Sci., pp. 31-45. Springer (2013) · Zbl 1381.68131 |
| [26] | Pin, J.-E.́: Mathematical Foundations of Automata Theory. In preparation (2016) |
| [27] | Pin, J.-É.: Open Problems About Regular Languages, 35 Years Later. World Scientific (2017) · Zbl 1402.68120 |
| [28] | Pin, J.-É., Straubing, H.: Monoids of upper triangular boolean matrices. In: Semigroups. Structure and Universal Algebraic Problems, vol. 39, pp. 259-272. North-Holland (1985) · Zbl 0635.20028 |
| [29] | Pin, J.-É., Weil, P.: Polynomial closure and unambiguous product. In: ICALP’95, Lect. Notes Comp. Sci., pp. 348-359. Springer (1995) · Zbl 1412.68145 |
| [30] | Pin, J.-É., Weil, P.: Polynomial closure and unambiguous product. Theory Comput. Syst. 30(4), 383-422 (1997) · Zbl 0872.68119 · doi:10.1007/BF02679467 |
| [31] | Pin, J.-É., Weil, P.: The wreath product principle for ordered semigroups. Commun. Algebra 30(12), 5677-5713 (2002) · Zbl 1017.06008 · doi:10.1081/AGB-120016005 |
| [32] | Place, T.: Separating regular languages with two quantifier alternations. In: LICS’15, pp. 202-213 (2015) · Zbl 1401.03067 |
| [33] | Place, T.: Separating regular languages with two quantifiers alternations. To appear. For a preliminary version see arXiv:1707.03295 (2018) · Zbl 1528.03173 |
| [34] | Place, T., Zeitoun, M.: Going higher in the first-order quantifier alternation hierarchy on words. In: ICALP’14, Lect. Notes Comp. Sci., pp. 342-353. Springer (2014) · Zbl 1407.03055 |
| [35] | Place, T., Zeitoun, M.: Separation and the successor relation. In: STACS’15, pp. 662-675. Leibniz-Zentrum fuer Informatik, Lipics (2015) · Zbl 1355.68169 |
| [36] | Place, T., Zeitoun, M.: The covering problem: a unified approach for investigating the expressive power of logics. In: MFCS’16, pp. 77:1-77:15. Leibniz-Zentrum fuer Informatik, Lipics (2016) · Zbl 1398.03158 |
| [37] | Place, T., Zeitoun, M.: Adding successor: a transfer theorem for separation and covering. arXiv:1709.10052 (2017) · Zbl 1433.03103 |
| [38] | Place, T., Zeitoun, M.: Concatenation hierarchies: new bottle, old wine. In: Weil, P. (ed.) CSR 2017, volume 10304 of Lect. Notes Comp. Sci., pp. 25-37. Springer (2017) · Zbl 1489.68134 |
| [39] | Place, T., Zeitoun, M.: The covering problem. arXiv:1707.03370 (2017) · Zbl 1448.03026 |
| [40] | Place, T., Zeitoun, M.: Going higher in first-order quantifier alternation hierarchies on words. arXiv:1707.05696 (2017) · Zbl 1407.03055 |
| [41] | Place, T., Zeitoun, M.: Separation for dot-depth two. In: LICS 2017, pp. 1-12. IEEE Computer Society (2017) · Zbl 1457.68146 |
| [42] | Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009) · Zbl 1188.68177 · doi:10.1017/CBO9781139195218 |
| [43] | Schützenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control. 8(2), 190-194 (1965) · Zbl 0131.02001 · doi:10.1016/S0019-9958(65)90108-7 |
| [44] | Simon, I.: Hierarchies of events of dot-depth one (1972) |
| [45] | Simon, I.: Piecewise testable events. In: Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, pp. 214-222. Springer (1975) · Zbl 0316.68034 |
| [46] | Simon, I.: Factorization forests of finite height. Theoret. Comp. Sci. 72(1), 65-94 (1990) · Zbl 0693.68044 · doi:10.1016/0304-3975(90)90047-L |
| [47] | Steinberg, B.: A delay theorem for pointlikes. Semigroup Forum 63(3), 281-304 (2001) · Zbl 1026.20043 · doi:10.1007/s002330010051 |
| [48] | Straubing, H.: A generalization of the Schützenberger product of finite monoids. Theoret. Comp. Sci. 13(2), 137-150 (1981) · Zbl 0456.20048 · doi:10.1016/0304-3975(81)90036-0 |
| [49] | Straubing, H.: Finite semigroup varieties of the form V * D. J Pure Appl. Algebra 36, 53-94 (1985) · Zbl 0561.20042 · doi:10.1016/0022-4049(85)90062-3 |
| [50] | Thérien, D.: Classification of finite monoids: the language approach. Theoret. Comp. Sci. 14(2), 195-208 (1981) · Zbl 0471.20055 · doi:10.1016/0304-3975(81)90057-8 |
| [51] | Thérien, D.: The power of diversity. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) Descriptional Complexity of Formal Systems, volume 6808 of Lect. Notes Comp. Sci., pp. 43-54. Springer (2011) · Zbl 1341.68127 |
| [52] | Thomas, W.: Classifying regular events in symbolic logic. J. Comput. System Sci. 25(3), 360-376 (1982) · Zbl 0503.68055 · doi:10.1016/0022-0000(82)90016-2 |
| [53] | Thomas, W.: An application of the Ehrenfeucht-Fraïssé game in formal language theory. Mémoires de la Société Mathématique de France 16, 11-21 (1984) · Zbl 0558.68064 · doi:10.24033/msmf.309 |
| [54] | Thomas, W.: A Concatenation game and the dot-depth hierarchy. In: Computation Theory and Logic, pp. 415-426. Springer, Berlin (1987) · Zbl 0643.68073 |
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.
