Document Open Access Logo

The Intersection Problem for Finite Monoids

Authors Lukas Fleischer, Manfred Kufleitner

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.30.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Lukas Fleischer
Manfred Kufleitner

Cite As Get BibTex

Lukas Fleischer and Manfred Kufleitner. The Intersection Problem for Finite Monoids. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.30

Abstract

We investigate the intersection problem for finite monoids, which asks for a given set of regular languages, represented by recognizing morphisms to finite monoids from a variety V, whether there exists a word contained in their intersection. Our main result is that the problem is PSPACE-complete if V is contained in DS and NP-complete if V is non-trivial and contained in DO. Our NP-algorithm for the case that V is contained in DO uses novel methods, based on compression techniques and combinatorial properties of DO. We also show that the problem is log-space reducible to the intersection problem for deterministic finite automata (DFA) and that a variant of the problem is log-space reducible to the membership problem for transformation monoids. In light of these reductions, our hardness results can be seen as a generalization of both a classical result by Kozen and a theorem by Beaudry, McKenzie and Thérien.

Subject Classification

Keywords
  • intersection problem
  • finite monoid
  • recognizing morphism
  • complexity

Metrics

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

References

  1. Jorge Almeida. Finite Semigroups and Universal Algebra. World Scientific, Singapore, 1994. Google Scholar
  2. László Babai, Eugene M. Luks, and Ákos Seress. Permutation groups in NC. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 409-420. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28439.
  3. László Babai, Eugene M. Luks, and Ákos Seress. Permutation groups in NC. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 409-420. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28439.
  4. Martin Beaudry. Membership testing in commutative transformation semigroups. Inf. Comput., 79(1):84-93, 1988. URL: http://dx.doi.org/10.1016/0890-5401(88)90018-1.
  5. Martin Beaudry. Membership Testing in Transformation Monoids. PhD thesis, McGill University, Montreal, Quebec, 1988. Google Scholar
  6. Martin Beaudry. Membership testing in threshold one transformation monoids. Inf. Comput., 113(1):1-25, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1062.
  7. Martin Beaudry, Pierre McKenzie, and Denis Thérien. The membership problem in aperiodic transformation monoids. J. ACM, 39(3):599-616, 1992. URL: http://dx.doi.org/10.1145/146637.146661.
  8. László Bernátsky. Regular expression star-freeness is PSPACE-complete. Acta Cybernetica, 13(1):1-21, 1997. Google Scholar
  9. Michael Blondin, Andreas Krebs, and Pierre McKenzie. The complexity of intersecting finite automata having few final states. Computational Complexity, 25(4):775-814, 2016. URL: http://dx.doi.org/10.1007/s00037-014-0089-9.
  10. Bogdan S. Chlebus. Domino-tiling games. J. Comput. Syst. Sci., 32(3):374-392, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90036-X.
  11. Sung Cho and Dung T. Huynh. Finite automaton aperiodicity is PSPACE-complete. Theoretical Computer Science, 88:96-116, 1991. Google Scholar
  12. Volker Diekert, Claudio Gutiérrez, and Christian Hagenah. The existential theory of equations with rational constraints in free groups is PSPACE-complete. Information and Computation, 202:105-140, 2005. Conference version in STACS 2001, LNCS 2010, 170-182, 2004. Google Scholar
  13. Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 36-41. IEEE Computer Society, 1980. URL: http://dx.doi.org/10.1109/SFCS.1980.34.
  14. Markus Holzer and Martin Kutrib. Descriptional and computational complexity of finite automata - A survey. Inf. Comput., 209(3):456-470, 2011. URL: http://dx.doi.org/10.1016/j.ic.2010.11.013.
  15. Tao Jiang and Bala Ravikumar. Minimal NFA problems are hard. In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez-Artalejo, editors, ICALP, volume 510 of Lecture Notes in Computer Science, pages 629-640. Springer, 1991. Google Scholar
  16. Dexter Kozen. Lower bounds for natural proof systems. In Proc. of the 18th Ann. Symp. on Foundations of Computer Science, FOCS'77, pages 254-266, Providence, Rhode Island, 1977. IEEE Computer Society Press. Google Scholar
  17. Klaus-Jörn Lange and Peter Rossmanith. The emptiness problem for intersections of regular languages. In Ivan M. Havel and Václav Koubek, editors, Mathematical Foundations of Computer Science 1992, 17th International Symposium, MFCS'92, Prague, Czechoslovakia, August 24-28, 1992, Proceedings, volume 629 of Lecture Notes in Computer Science, pages 346-354. Springer, 1992. URL: http://dx.doi.org/10.1007/3-540-55808-X_33.
  18. Jean-Éric Pin. Varieties of Formal Languages. North Oxford Academic, London, 1986. Google Scholar
  19. Marcel-Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965. Google Scholar
  20. Pascal Tesson and Denis Thérien. Diamonds are forever: The variety DA. In Gracinda Maria dos Gomes Moreira da Cunha, Pedro Ventura Alves da Silva, and Jean-Éric Pin, editors, Semigroups, Algorithms, Automata and Languages, Coimbra (Portugal) 2001, pages 475-500. World Scientific, 2002. 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 About DROPS Imprint Privacy Contact