×
Blanchet-Sadri, F.

Games, equations and the dot-depth hierarchy. (English) Zbl 0682.03015

Comput. Math. Appl. 18, No. 9, 809-822 (1989).
Summary: This paper studies the fine structure of the Straubing hierarchy of star- free languages. The monoid varieties of some sublevels of level one of the hierarchy are shown to be characterized by certain natural equation systems. Those are then generalized to definitions of equation systems satisfied in monoid varieties of higher sublevels. A version of the Ehrenfeucht-Fraisse game is used to verify equations.

Cited in 16 Documents

MSC:

03C05 Equational classes, universal algebra in model theory
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.

Keywords:

fine structure of the Straubing hierarchy of star-free languages; monoid varieties; Ehrenfeucht-Fraisse game
Cite Review PDF
Full Text: DOI

References:

[1] Blanchet-Sadri, F., Some logical characterizations of the dot-depth hierarchy and applications, Technical Report No. 88-03 of the Department of Mathematics and Statistics of McGill University, 1-44 (1988)
[2] Pin, J. E., Hierarchies de concatenation, RAIRO Inf. theor., 18, 23-46 (1984) · Zbl 0559.68062
[3] Knast, R., A semigroup characterization of dot-depth one languages, RAIRO Inf. theor., 17, 321-330 (1983) · Zbl 0522.68063
[4] Schützenberger, M. P., On finite monoids having only trivial subgroups, Inf. Control, 8, 190-194 (1965) · Zbl 0131.02001
[5] McNaughton, R.; Papert, S., Counter-free Automata (1971), MIT Press: MIT Press Cambridge, Mass · Zbl 0232.94024
[6] Eilenberg, S., (Automata, Languages and Machines, Vol. B (1976), Academic Press: Academic Press New York) · Zbl 0359.94067
[7] Pin, J. E., Varieties de Langages Formels (1984), Masson: Masson Paris · Zbl 0636.68093
[8] Cohen, R. S.; Brzozowski, J. A., Dot-depth of star-free events, J. Comput. Syst. Sci., 5, 1-16 (1971) · Zbl 0217.29602
[9] Straubing, H., Finite semigroup varieties of the form \(V ∗ D\), J. Pure Appl. Algebra, 36, 53-94 (1985) · Zbl 0561.20042
[10] Straubing, H., Semigroups and languages of dot-depth two, (Proc. 13th ICALP, Lecture Notes in Computer Science (1986), Springer: Springer New York), 416-423 · Zbl 0596.68056
[11] 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
[12] Thomas, W., An application of the Ehrenfeucht-Fraisse game in formal language theory, Soc. math. France \((2^e\) Ser.), 16, 11-21 (1984) · Zbl 0558.68064
[13] Thomas, W., Classifying regular events in symbolic logic, J. Comput. Syst. Sci., 25, 360-376 (1982) · Zbl 0503.68055
[14] Perrin, D.; Pin, J. E., First-order logic and star-free sets, J. Comput. Syst. Sci., 32, 393-406 (1986) · Zbl 0618.03015
[15] Simon, I., Piecewise testable events, (Proc. 2nd GI Conf. Lecture Notes in Computer Science 33 (1975), Springer: Springer Berlin), 214-222 · Zbl 0316.68034
[16] Tilson, B., Categories as algebra, J. Pure Appl. Algebra, 48, 83-198 (1987) · Zbl 0627.20031
[17] Simon, I., Hierarchies of events of dot-depth one, (Ph.D. Thesis (1972), University of Waterloo)
[18] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[19] Enderton, H. B., A Mathematical Introduction to Logic (1972), Academic Press: Academic Press New York · Zbl 0298.02002
[20] Ladner, R. E., Application of model-theoretic games to discrete linear orders and finite automata, Inf. Control, 33, 281-303 (1977) · Zbl 0387.68037
[21] McNaughton, R., Algebraic decision procedures for local testability, J. Math. Syst. theor., 8 (1974) · Zbl 0287.02022
[22] Brzozowski, J. A.; Simon, I., Characterizations of locally testable events, Discrete Math., 4, 243-271 (1973) · Zbl 0255.94032
[23] Rosenstein, J. G., Linear Orderings (1982), Academic Press: Academic Press New York · Zbl 0179.01303
[24] Fraisse, R., Cours de Logique Mathematique (1972), Tome 2. Gauthier-Villars: Tome 2. Gauthier-Villars Paris · Zbl 0247.02003
[25] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundam. Math., 49, 129-141 (1961) · Zbl 0096.24303
[26] Kleene, S. C., Representation of events in nerve nets and finite automata, (Automata Studies (1956), Princeton Univ. Press: Princeton Univ. Press Princeton, N.J), 3-42
[27] Therien, D., Classification of regular languages by congruences, (Ph.D. Thesis (1980), University of Waterloo)
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.