×

Characterizing classes of regular languages using prefix codes of bounded synchronization delay. (English) Zbl 1373.68291

Summary: This paper is motivated by the work of Schützenberger on codes with bounded synchronization delay. He was interested in characterizing those regular languages where groups in the syntactic monoid belong to a variety \(\mathbf{H}\). On the language side he allowed the operations union, intersection, concatenation and modified Kleene-star involving a mapping of a prefix code of bounded synchronization delay to a group \(G\in\mathbf{H}\), but no complementation. In our notation, this leads to the language classes \(\mathbf{SD_H}(A^\infty)\). Our main result shows that \(\mathbf{SD_H}(A^\infty)\) coincides with the class of languages having syntactic monoids where all subgroups are in \(\mathbf{H}\). We show that this statement holds for all varieties \(\mathbf{H}\) of finite groups, whereas Schützenberger proved this result for varieties \(\mathbf{H}\) containing abelian groups, only. Our method shows the result for all \(\mathbf{H}\) simultaneously on finite and infinite words. Furthermore, we introduce the notion of local Rees extension which refers to a restricted type of the classical Rees extension. We give a decomposition of a monoid in terms of its groups and local Rees extensions. This gives a somewhat similar, but simpler decomposition than in the synthesis theorem of Rhodes and Allen. Moreover, we need a singly exponential number of operations, only. Finally, our decomposition yields an answer to a question in a recent paper of Almeida and Klíma about varieties that are closed under Rees extensions.

MSC:

68Q70 Algebraic theory of languages and automata
20M07 Varieties and pseudovarieties of semigroups
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata

References:

[1] Almeida, J. and Klíma, O., On the irreducibility of pseudovarieties of semigroups, J. Pure Appl. Algebra220(4) (2016) 1517-1524. · Zbl 1336.20055
[2] Arnold, A., A syntactic congruence for rational \(\omega \)-languages, Theor. Comput. Sci.39 (1985) 333-335. · Zbl 0578.68057
[3] Birget, J.-C. and Rhodes, J. L., Almost finite expansions of arbitrary semigroups, J. Pure Appl. Algebra32(3) (1984) 239-287. · Zbl 0546.20055
[4] Birget, J.-C. and Rhodes, J. L., Group theory via global semigroup theory, J. Algebra120(2) (1989) 284-300. · Zbl 0668.20048
[5] Büchi, J. R., On a decision method in restricted second-order arithmetic, in Proc. Int. Congsr. for Logic, Methodology, and Philosophy of Science (Stanford University Press, 1962), pp. 1-11. · Zbl 0147.25103
[6] Costa, A. and Steinberg, B., The Schützenberger category of a semigroup, Semigroup Forum91 (2014) 543-559. · Zbl 1343.20064
[7] Diekert, V. and Gastin, P., First-order definable languages, in Logic and Automata: History and Perspectives, Texts in Logic and Games, eds. Flum, J., Grädel, E. and Wilke, Th. (Amsterdam University Press, 2008), pp. 261-306. · Zbl 1234.03024
[8] Diekert, V. and Kufleitner, M., Omega-rational expressions with bounded synchronization delay, Theory Comput. Syst.56 (2015) 686-696. · Zbl 1343.68135
[9] Diekert, V. and Kufleitner, M., A survey on the local divisor technique, Theor. Comput. Sci.610 (2015) 13-23. · Zbl 1332.68147
[10] Diekert, V., Kufleitner, M., Rosenberger, G. and Hertrampf, U., Discrete Algebraic Methods. Arithmetic, Cryptography, Automata and Groups (Walter de Gruyter, 2016). · Zbl 1350.00001
[11] Diekert, V., Kufleitner, M. and Weil, P., Star-free languages are Church-Rosser congruential, Theor. Comput. Sci.454 (2012) 129-135. · Zbl 1279.68147
[12] Diekert, V. and Rozenberg, G. (eds.), The Book of Traces (World Scientific, Singapore, 1995).
[13] Eilenberg, S., Automata, Languages, and Machines, Vol. B (Academic Press, New York, 1976). · Zbl 0359.94067
[14] Kleene, S. C., Representation of events in nerve nets and finite automata, in Automata Studies, eds. (Shannon, C. E. and McCarthy, J.) , Vol. 34 (Princeton University Press, 1956), pp. 3-40.
[15] Lallement, G., Semigroups and Combinatorial Applications, (John Wiley & Sons, New York, 1979). · Zbl 0421.20025
[16] Perrin, D., Recent results on automata and infinite words, in Mathematical Foundations of Computer Sciences, , Vol. 176 (Springer, Berlin, 1984), pp. 134-148. · Zbl 0577.68076
[17] Perrin, D. and Pin, J.-É., Infinite Words, , Vol. 141 (Elsevier, Amsterdam, 2004). · Zbl 1094.68052
[18] Pin, J.-É., Varieties of Formal Languages (North Oxford Academic, London, 1986). · Zbl 0632.68069
[19] Rhodes, J. L. and Allen, D., Synthesis of the classical and modern theory of finite semigroups, Adv. Math.11(2) (1973) 238-266. · Zbl 0269.20047
[20] Rhodes, J. L. and Steinberg, B., The \(\mathfrak{q} \)-Theory of Finite Semigroups, (Springer, 2009). · Zbl 1186.20043
[21] Schützenberger, M.-P., On finite monoids having only trivial subgroups, Inform. Control8 (1965) 190-194. · Zbl 0131.02001
[22] Schützenberger, M.-P., Sur les monoides finis dont les groupes sont commutatifs, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge8(R-1) (1974) 55-61. · Zbl 0294.20056
[23] Schützenberger, M.-P., Sur certaines opérations de fermeture dans les langages rationnels, in Symposia Mathematica, Vol. XV (Convegno di Informatica Teorica, INDAM, Roma, 1973) (Academic Press, 1975), pp. 245-253. · Zbl 0359.20066
[24] Straubing, H., Families of recognizable sets corresponding to certain varieties of finite monoids, J. Pure Appl. Algebra15(3) (1979) 305-318. · Zbl 0414.20056
[25] Straubing, H., Finite Automata, Formal Logic, and Circuit Complexity (Birkhäuser, Boston, 1994). · Zbl 0816.68086
[26] Straubing, H., Thérien, D. and Thomas, W., Regular languages defined with generalized quantifiers, Inform. Comput.118(2) (1995) 289-301. · Zbl 0826.68072
[27] Thomas, W., Automata on infinite objects, in Handbook of Theoretical Computer Science, ed. van Leeuwen, J. (Elsevier Science Publishers B. V., 1990), pp. 133-191. · Zbl 0900.68316
[28] T. Walter, Local Divisors in Formal Languages, Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart (2016), http://dx.doi.org/10.18419/opus-8970.
[29] Wilke, T., An algebraic theory for regular languages of finite and infinite words, Int. J. Algebra Comput.3 (1993) 447-489. · Zbl 0791.68116
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.