Document Open Access Logo

The Power of Programs over Monoids in DA

Authors Nathan Grosshans, Pierre McKenzie, Luc Segoufin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.2.pdf
  • Filesize: 0.52 MB
  • 20 pages

Document Identifiers

Author Details

Nathan Grosshans
Pierre McKenzie
Luc Segoufin

Cite AsGet BibTex

Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. The Power of Programs over Monoids in DA. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.2

Abstract

The program-over-monoid model of computation originates with Barrington's proof that it captures the complexity class NC^1. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as DA satisfies tameness and hence that the regular languages recognized by programs over monoids in DA are precisely those recognizable in the classical sense by morphisms from QDA. Third, we show by contrast that the well studied class of monoids called J is not tame and we exhibit a regular language, recognized by a program over a monoid from J, yet not recognizable classically by morphisms from the class QJ. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from DA.
Keywords
  • Programs over monoids
  • DA
  • lower-bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklós Ajtai. Σ₁¹-formulae on finite structures. In Ann. Pure and Appl. Logic, volume 24, pages 1-48, 1983. Google Scholar
  2. Jorge Almeida. A syntactical proof of locality of DA. Int. J. of Algebra and Computation (IJAC), 6(2):165-178, 1996. Google Scholar
  3. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. J. Comput. Syst. Sci., 38(1):150-164, 1989. Google Scholar
  4. David A. Mix Barrington, Kevin J. Compton, Howard Straubing, and Denis Thérien. Regular languages in NC¹. J. Comput. Syst. Sci., 44(3):478-499, 1992. Google Scholar
  5. David A. Mix Barrington, Howard Straubing, and Denis Thérien. Non-uniform automata over groups. Inf. Comput., 89(2):109-132, 1990. Google Scholar
  6. David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC^1. J. ACM, 35(4):941-952, 1988. Google Scholar
  7. Laura Chaubard, Jean-Éric Pin, and Howard Straubing. Actions, wreath products of C-varieties and concatenation product. Theoretical Computer Science, 356(1-2):73-89, 2006. Google Scholar
  8. Luc Dartois. Méthodes algébriques pour la théorie des automates. PhD thesis, Université Paris Diderot, Paris, 2014. Google Scholar
  9. Luc Dartois and Charles Paperman. Adding modular predicates. CoRR, abs/1401.6576, 2014. URL: http://arxiv.org/abs/1401.6576.
  10. Samuel Eilenberg. Automata, Languages, and Machines, volume A. Academic Press, New York, 1974. Google Scholar
  11. Samuel Eilenberg. Automata, Languages, and Machines, volume B. Academic Press, New York, 1976. Google Scholar
  12. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  13. Ricard Gavaldà and Denis Thérien. Algebraic characterizations of small classes of Boolean functions. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2607 of Lecture Notes in Computer Science, pages 331-342. Springer, 2003. Google Scholar
  14. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), pages 6-20. ACM, 1986. Google Scholar
  15. Kenneth Krohn and John L. Rhodes. Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. In Trans. Amer. Math. Soc., volume 116, pages 450-464, 1965. Google Scholar
  16. Alexis Maciel, Pierre Péladeau, and Denis Thérien. Programs over semigroups of dot-depth one. Theor. Comput. Sci., 245(1):135-148, 2000. Google Scholar
  17. Ward D. Maurer and John L. Rhodes. A property of finite simple non-abelian groups. In Amer. Math. Soc., volume 16, pages 552-554, 1965. Google Scholar
  18. Pierre McKenzie, Pierre Péladeau, and Denis Thérien. NC¹: The automata-theoretic viewpoint. Computational Complexity, 1:330-359, 1991. Google Scholar
  19. Charles Paperman. Circuits booléens, prédicats modulaires et langages réguliers. PhD thesis, Université Paris Diderot, Paris, 2014. Google Scholar
  20. Pierre Péladeau. Classes de circuits booléens et variétés de monoïdes. PhD thesis, Université Pierre-et-Marie-Curie (Paris-VI), Paris, France, 1990. Google Scholar
  21. Pierre Péladeau, Howard Straubing, and Denis Thérien. Finite semigroup varieties defined by programs. Theor. Comput. Sci., 180(1-2):325-339, 1997. Google Scholar
  22. Jean-Éric Pin. Varieties of formal languages. North Oxford, London and Plenum, New-York, 1986. (Traduction de Variétés de langages formels). Google Scholar
  23. Jean-Éric Pin and Howard Straubing. Some results on 𝒞-varieties. RAIRO-Theor. Inf. Appl., 39(1):239-262, 2005. Google Scholar
  24. Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes, 41(4):333-338, 1987. Google Scholar
  25. Jan Reiterman. The Birkhoff theorem for finite algebras. algebra universalis, 14(1):1-10, 1982. Google Scholar
  26. Imre Simon. Piecewise testable events. In Automata Theory and Formal Languages, 2nd GI Conference, volume 33 of Lecture Notes in Computer Science, pages 214-222. Springer, 1975. Google Scholar
  27. Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pages 77-82. ACM, 1987. Google Scholar
  28. Pascal Tesson. Computational Complexity Questions Related to Finite Monoids and Semigroups. PhD thesis, McGill University, Montreal, Canada, 2003. Google Scholar
  29. Pascal Tesson and Denis Thérien. The computing power of programs over finite monoids. J. Autom. Lang. Comb., 7(2):247-258, November 2001. Google Scholar
  30. Pascal Tesson and Denis Thérien. Diamonds are forever: the variety DA. Semigroups, algorithms, automata and languages, 1:475-500, 2002. Google Scholar
  31. Bret Tilson. Categories as algebra: An essential ingredient in the theory of monoids. J. of Pure and Applied Algebra, 48(1-2), 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact