Languages of dot-depth 3/2. (English) Zbl 1141.68037
Summary: We show that level 3/2 of the dot-depth hierarchy is decidable. More precisely, we identify a pattern \(\mathbb{B}\) such that the following holds: If \(F\) is a deterministic finite automaton that accepts \(L\), then \(L\) belongs to level 3/2 of the dot-depth hierarchy if and only if \(F\) does not have \(\mathbb{B}\) as a subgraph in its transition graph. The latter condition can be tested in nondeterministic logarithmic space.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Arfi, M.: Polynomial operations on rational languages. In: Proceedings 4th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 247, pp. 198–206. Springer, New York (1987) · Zbl 0635.68078 |
| [2] | Arfi, M.: Opérations polynomiales et hiérarchies de concaténation. Theor. Comput. Sci. 91, 71–84 (1991) · Zbl 0751.68031 · doi:10.1016/0304-3975(91)90268-7 |
| [3] | Brzozowski, J.A., Knast, R.: The dot-depth hierarchy of star-free languages is infinite. J. Comput. Syst. Sci. 16, 37–55 (1978) · Zbl 0368.68074 · doi:10.1016/0022-0000(78)90049-1 |
| [4] | Cohen, R.S., Brzozowski, J.A.: Dot-depth of star-free events. J. Comput. Syst. Sci. 5, 1–16 (1971) · Zbl 0217.29602 · doi:10.1016/S0022-0000(71)80003-X |
| [5] | Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic, New York (1976) |
| [6] | Glaßer, C.: A normal form for classes of concatenation hierarchies. Technical Report 216, Inst. für Informatik, Univ. Würzburg (1998) |
| [7] | Glaßer, C., Schmitz, H.: Decidable hierarchies of starfree languages. In: Proceedings 20th Conference on the Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1974, pp. 503–515. Springer, New York (2000) · Zbl 1044.68091 |
| [8] | Glaßer, C., Schmitz, H.: Languages of dot-depth 3/2. In: Proceedings 17th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1770, pp. 555–566. Springer, New York (2000) · Zbl 0962.68093 |
| [9] | Glaßer, C., Schmitz, H.: Level 5/2 of the Straubing-Thérien-hierarchy for two-letter alphabets. In: Proceedings 5th International Conference on Developments in Language Theory. Lecture Notes in Computer Science, vol. 2295, pp. 251–261. Springer, New York (2001) · Zbl 1073.68046 |
| [10] | Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17, 935–938 (1988) · Zbl 0668.68056 · doi:10.1137/0217058 |
| [11] | McNaughton, R.: Algebraic decision procedures for local testablility. Math. Syst. Theor. 8, 60–76 (1974) · Zbl 0287.02022 · doi:10.1007/BF01761708 |
| [12] | McNaughton, R., Papert, S.: Counterfree Automata. MIT Press, Cambridge (1971) · Zbl 0232.94024 |
| [13] | Pin, J.-E.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 679–746. Springer, New York (1996) |
| [14] | Pin, J.-E.: Bridges for concatenation hierarchies. In: Proceedings 25th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 1443, pp. 431–442. Springer, New York (1998) · Zbl 0909.68113 |
| [15] | Pin, J.-E., Weil, P.: Polynomial closure and unambiguous product. Theory Comput. Syst. 30, 383–422 (1997) · Zbl 0872.68119 |
| [16] | Pin, J.E., Weil, P.: The wreath product principle for ordered semigroups. Commun. Algebra 30, 5677–5713 (2002) · Zbl 1017.06008 · doi:10.1081/AGB-120016005 |
| [17] | Schützenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8, 190–194 (1965) · Zbl 0131.02001 · doi:10.1016/S0019-9958(65)90108-7 |
| [18] | Simon, I.: Hierarchies of events with dot-depth one. Ph.D. thesis, University of Waterloo (1972) |
| [19] | Straubing, H.: A generalization of the Schützenberger product of finite monoids. Theor. Comput. Sci. 13, 137–150 (1981) · Zbl 0456.20048 · doi:10.1016/0304-3975(81)90036-0 |
| [20] | 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 |
| [21] | Straubing, H.: Semigroups and languages of dot-depth two. Theor. Comput. Sci. 58, 361–378 (1988) · Zbl 0655.18004 · doi:10.1016/0304-3975(88)90034-5 |
| [22] | Szelepcsényi, R.: The method of forcing for nondeterministic automata. Bull. EATCS 33, 96–100 (1987) · Zbl 0664.68082 |
| [23] | Thérien, D.: Classification of finite monoids: the language approach. Theor. Comput. Sci. 14, 195–208 (1981) · Zbl 0471.20055 · doi:10.1016/0304-3975(81)90057-8 |
| [24] | Thomas, W.: Classifying regular events in symbolic logic. J. Comput. Syst. Sci. 25, 360–376 (1982) · Zbl 0503.68055 · doi:10.1016/0022-0000(82)90016-2 |
| [25] | Thomas, W.: An application of the Ehrenfeucht–Fraïssé game in formal language theory. Soc. Math. France Mém. 16(2), 11–21 (1984) · Zbl 0558.68064 |
| [26] | Wagner, K.W.: Leaf language classes. In: Proceedings International Conference on Machines, Computations, and Universality. Lecture Notes in Computer Science, vol. 3354. Springer, New York (2004) |
| [27] | Weil, P.: Algebraic recognizability of languages. In: Proceedings 29th Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 3153, pp. 149–175. Springer, New York (2004) · Zbl 1097.68078 |
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.
