LIPIcs.STACS.2018.30.pdf
- Filesize: 0.56 MB
- 14 pages
Document
The Intersection Problem for Finite Monoids
Authors
-
Part of:
Volume:
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-02-27
Cite AsGet 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
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.
Keywords
- intersection problem
- finite monoid
- recognizing morphism
- complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jorge Almeida. Finite Semigroups and Universal Algebra. World Scientific, Singapore, 1994.
- 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.
- 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.
- 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.
-
Martin Beaudry. Membership Testing in Transformation Monoids. PhD thesis, McGill University, Montreal, Quebec, 1988.
- 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.
- 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.
-
László Bernátsky. Regular expression star-freeness is PSPACE-complete. Acta Cybernetica, 13(1):1-21, 1997.
- 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.
- 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.
-
Sung Cho and Dung T. Huynh. Finite automaton aperiodicity is PSPACE-complete. Theoretical Computer Science, 88:96-116, 1991.
-
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.
- 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.
- 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.
-
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.
-
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.
- 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.
-
Jean-Éric Pin. Varieties of Formal Languages. North Oxford Academic, London, 1986.
-
Marcel-Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965.
-
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.