Concatenation hierarchies

One of the most fascinating problem in automata theory is the so-called "dot-depth 2" problem. It admits several equivalent formulations
  1. Combinatorial version. Is there an algorithm to decide whether a given rational language is a Boolean combination of languages of the form A*0a1A*1 ... anA*n, where the ai's are letters and the Ai's are subsets of the alphabet ?

  2. Algebraic version. Is there an algorithm to decide whether a given finite monoid divides, for some n, a monoid of n by n upper-triangular Boolean matrices ?

  3. Logical version. Is there an algorithm to decide whether a first order formula of Büchi's sequential calculus is equivalent (on finite words) with a Boolean combination of Σ2-formulas ?

  4. History and known results

  5. References

1. Combinatorial version.

Let A be an alphabet. The definition of star-free subsets of A* makes use of two different types of operations: Boolean operations and concatenation product. By alternating the use of these two operations, one gets a hierarchy, called the concatenation hierarchy, defined as follows.
  1. The sets of level 0 are the empty set and A*,
  2. For every integer n > 0, the sets of level n+1/2 are the finite unions of sets of the form
    L0a1L1a2 ... akLk
    where L0, L1, ..., Lk are sets of level n and a1, ..., ak are letters.
  3. For every integer n > 0, the sets of level n+1 are the finite Boolean combinations of sets of level n+1/2.
Note that a set of level m is also a set of level n for every n > m. The following results are known (Brzozowski and Knast, Perrin and Pin).
  1. For every n> 0, the sets of level n are closed under union, intersection, and complement.
  2. For every n> 0, the sets of level n+1/2 are closed under union, intersection, and concatenation product.
  3. The hierarchy is strict: if A contains at least two letters, then for every n, there exist some sets of level n+1 that are not of level n + 1/2 and some sets of level n + 1/2 that are not of level n.

2. Algebraic version.

A monoid M divides a monoid N if M is a quotient of a submonoid of N.
The Boolean semiring is B = {0, 1}. Addition and multiplication are given in the following tables
+ 0 1
0 0 1
1 1 1
x 0 1
0 0 0
1 0 1
Matrix multiplication is defined in the usual way. A Boolean upper triangular matrix is a matrix whith 0 entries in position (i, j) if i > j. For instance
1 0 1 1
0 0 0 1
0 0 1 1
0 0 0 1

is a 4 x 4 upper triangular Boolean matrix. The set Tn of n x n upper triangular matrices is a monoid under the multiplication of Boolean matrices. The problem is to decide whether a given finite monoid divides one of the monoids Tn, for some n > 0.
The corresponding problem for the monoids Un of unitriangular matrices has been solved: a monoid divides a monoid Un for some n > 0, if and only if it is J-trivial.

3. Logical version.

Büchi's sequential calculus is a logical formalism to specify some combinatorial properties of a finite word, for instance "the factor bba occurs three times in the word, but the factor bbb does not occur". Thus, each logical sentence of this calculus defines a language, namely the set of all words that satisfy the property expressed by the formula.

More precisely, to each word u ∈ A+ is associated a structure
Mu = ({1, 2, ..., ¦u¦}, <, (a)a ∈ A )
where < denotes the usual order on {1, 2, ..., ¦u¦} and a is the set of all i such that the i-th letter of u is an a. For instance, if A = {a, b} and u = abaab, then a = {1, 3, 4} and b = {2, 5}. The logical language appropriate to such models has < and the a's as non logical symbols, and formulas are built in the standard way by using these non-logical symbols, variables, Boolean connectives, equality between elements (positions) and quantifiers.
Given a sentence φ, we denote by L(φ) the set of all words which satisfy φ, when words are considered as models. For instance, the formula
∃ i ∃ j  i < j   ∧   a i   ∧   b j
defines the language A*aA*bA*.
Two formulas are said to be (elementary) equivalent if they define the same languages.
It is well known that every logical formula can be written in prenex formal form, that is to say, of the form φ = Q(x1, ...,xk)ψ where Q(x1, ...,xk) is a sequence of existential or universal quantifiers on the variables x1, ...,xk and where ψ is quantifier free. If Q(x1, ...,xk) is formed of n blocks of quantifiers such that the first block contains only existential quantifiers (note that this first block may be empty), the second block universal quantifiers, etc., we say that φ is a Σn-formula. We denote by Σn the set of the Σn-formulae and by BΣn the set of Boolean combinations (Boolean operations on formulae comprise conjunction, disjunction and negation) of Σn-formulae.

The connection between the two hierarchies was established by Thomas (see also Perrin and Pin): a subset of A* is of level n (resp. n+1/2) if and only if it is BΣn-definable (resp. Σn+1-definable).

4. History and known results

next Section under construction...

5. References

  1. J. Almeida, 1990, Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon, J. Pure Appl. Algebra 69, 205--218.
  2. M. Arfi, 1987, Polynomials operations and relational languages, 4th STACS, Lecture Notes in Computer Science 247, Springer, 198--206.
  3. M. Arfi, 1991, Opérations polynomiales et hiérarchies de concaténation, Theoret. Comput. Sci. 91, 71--84.
  4. D. Beauquier and J.E. Pin, 1989, Factors of words, in Automata, Languages and Programming, (G. Ausiello, M. Dezani-Ciancaglini and S. Ronchi Della Rocca, eds.), Lecture Notes in Comput. Sci., 372, Springer, 63--79.
  5. D. Beauquier and J.E. Pin, 1991, Languages and scanners, Theoret. Comput. Sci. 84 3--21.
  6. J.A. Brzozowski and R. Knast, 1978, The dot-depth hierarchy of star-free languages is infinite, J. Comput. System Sci. 16 37--55.
  7. J.A. Brzozowski and I. Simon, 1973, Characterizations of locally testable languages, Discrete Math. 4, 243-271.
  8. J.R. Büchi, 1960, Weak second-order arithmetic and finite automata, Z. Math. Logik und Grundl. Math. 6, 66--92.
  9. J.R. Büchi, 1962, On a decision method in restricted second-order arithmetic, in Proc. 1960 Int. Congr. for Logic, Methodology and Philosophy of Science, Stanford Univ. Press, Standford, 1--11.
  10. J.R. Büchi and L.H. Landweber, 1969, Definability in the monadic second-order theory of successors, J. Symbolic Logic 34 166--170.
  11. S. Cho and D.T. Huynh, 1991, Finite automaton aperiodicity is PSPACE-complete, Theoret. Comput. Sci. 88 99--116.
  12. D. Cowan, 1993, Inverse monoids of dot-depth 2, Int. Jour. Alg. and Comp., to appear.
  13. S. Eilenberg, 1974, Automata, languages and machines, Vol. A, Academic Press, New York.
  14. S. Eilenberg, 1976, Automata, languages and machines, Vol. B, Academic Press, New York.
  15. C.C. Elgot, 1961, Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc. 98, 21--52.
  16. H. Gaifman, 1982, On local and non-local properties, in Proc. of the Herbrandt Symposium, Logic Colloquium'81 (J. Stern, ed.), Studies in Logic 107, North-Holland, Amsterdam, 105--135.
  17. C. Glasser and H. Schmitz, Languages of dot-depth 3/2, Proceedings 17th Symposium on Theoretical Aspects of Computer Science, Lect. Notes in Comp. Sci. 1770, Springer Verlag, (2000), 555--566.
  18. C. Glasser and H. Schmitz, Decidable Hierarchies of Starfree Languages, Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Lect. Notes in Comp. Sci. 1974, Springer-Verlag, (2000), 503--515.
  19. C. Glasser and H. Schmitz, Concatenation Hierarchies and Forbidden Patterns, Technical Report No. 256, University of Wuerzburg, (2000).
  20. R. Knast, A semigroup characterization of dot-depth one languages, RAIRO Inform. Théor.17, (1983) 321--330.
  21. R. Knast, Some theorems on graph congruences, RAIRO Inform. Théor. 17, (1983) 331--342.
  22. G. Lallement, 1979, Semigroups and combinatorial applications, Wiley, New York.
  23. R. McNaughton, 1974, Algebraic decision procedures for local testability, Math. Syst. Theor. 8, 60-76.
  24. R. McNaughton and S. Pappert, 1971, Counter-free Automata, MIT Press.
  25. D. Perrin and J.E. Pin, First order logic and star-free sets, J. Comput. System Sci. 32, 1986, 393--406.
  26. J.-E. Pin, 1984, Hiérarchies de concaténation, RAIRO Informatique Théorique 18 23--46.
  27. J.-E. Pin, 1984, Variétés de langages formels, Masson, Paris; English translation: 1986, Varieties of formal languages, Plenum, New-York.
  28. J.-E. Pin, Logic, Semigroups and Automata on Words, Annals of Mathematics and Artificial Intelligence 16 (1996), 343--384. Abstract
  29. J.-E. Pin, A variety theorem without complementation, Russian Mathematics (Izvestija vuzov.Matematika) 39 (1995), 80--90. Abstract
  30. J.-E. Pin, Logic On Words, Bulletin of the European Association of Theoretical Computer Science 54 (1994), 145--165.
    Current Trends in Theoretical Computer Science, Entering the 21st Century, eds. G. Paun, G. Rozenberg and A. Salomaa, Word Scientific, (2001), 254--273. Abstract
  31. J.-E. Pin, Algebraic tools for the concatenation product, à paraître dans Theoretical Computer Science Abstract
  32. J.-E. Pin, A. Pinguet et P. Weil, Ordered categories and ordered semigroups, à paraître dans Communications in Algebra. Abstract
  33. J.-E. Pin and H. Straubing, 1981, Monoids of upper triangular matrices, Colloquia Mathematica Societatis Janos Bolyai 39, Semigroups, Szeged, 259--272.
  34. J.-E. Pin et P. Weil, Semidirect products of ordered semigroups, à paraître dans Communications in Algebra. Abstract
  35. J.-E. Pin et P. Weil, The wreath product principle for ordered semigroups, à paraître dans Communications in Algebra. Abstract
  36. J.-E. Pin et P. Weil, A conjecture on the concatenation product, à paraître dans ITA Abstract
  37. M.P. Schützenberger, 1965, On finite monoids having only trivial subgroups, Information and Control 8, 190--194.
  38. I. Simon, 1975, Piecewise testable events, Proc. 2nd GI Conf., Lect. Notes in Comp. Sci. 33, Springer, Berlin, 214--222.
  39. I. Simon, The product of rational languages, Proceedings of ICALP 1993, Lect. Notes in Comp. Sci. 700, Springer Verlag, Berlin, Heidelberg, New York, (1993), 430--444.
  40. J. Stern, 1985, Characterization of some classes of regular events, Theoret. Comp. Sci. 35, 17--42.
  41. J. Stern, 1985, Complexity of some problems from the theory of automata, Inform. and Control 66, 163--176.
  42. H. Straubing, 1979, Aperiodic homomorphisms and the concatenation product of recognizable sets, Journal of Pure and Applied Algebra 15, 319--327.
  43. H. Straubing, Finite semigroups varieties of the form V * D, J. Pure Appl. Algebra 36, (1985), 53--94.
  44. H. Straubing, 1988, Semigroups and languages of dot-depth two, Theoret. Comp. Sci. 58, 361--378.
  45. H. Straubing and D. Thérien, 1985, Partially ordered finite monoids and a theorem of I. Simon, J. of Algebra 119, 393--399.
  46. H. Straubing, D. Thérien and W. Thomas, 1988, Regular Languages Defined with Generalized Quantifiers, in Proc. 15th ICALP, Springer Lecture Notes in Computer Science 317, 561--575.
  47. H. Straubing and P. Weil, 1992, On a conjecture concerning dot-depth two languages, Theoret. Comp. Sci. 104, 161--183.
  48. D. Thérien, Classification of finite monoids: the language approach, Theoret. Comp. Sci. 14, (1981), 195--208.
  49. D. Thérien and A. Weiss, 1985, Graph congruences and wreath products, J. Pure Applied Algebra 35, 205-215.
  50. W. Thomas, 1982, Classifying regular events in symbolic logic, J. Comput. Syst. Sci 25, 360--375.
  51. P. Weil, 1988, Inverse monoids and the dot-depth hierarchy, Ph. D. Dissertation, University of Nebraska, Lincoln.
  52. P. Weil, 1989, Inverse monoids of dot-depth two, Theoret. Comp. Sci. 66, 233--245.
  53. P. Weil, 1993, Some results on the dot-depth hierarchy, Semigroup Forum 46, , 352--370.

Last modified 03/29/2008