Document Open Access Logo

Decomposing Finite Languages

Author Daniel Alexander Spenner

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.83.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Daniel Alexander Spenner
  • Technische Universität Dortmund, Germany

Acknowledgements

I want to thank Thomas Schwentick for his advice and encouragement.

Cite As Get BibTex

Daniel Alexander Spenner. Decomposing Finite Languages. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.83

Abstract

The paper completely characterizes the primality of acyclic DFAs, where a DFA 𝒜 is prime if there do not exist DFAs 𝒜_1,… ,𝒜_t with ℒ(𝒜) = ⋂_{i=1}^t ℒ(𝒜_i) such that each 𝒜_i has strictly less states than the minimal DFA recognizing the same language as 𝒜. A regular language is prime if its minimal DFA is prime. Thus, this result also characterizes the primality of finite languages.
Further, the NL-completeness of the corresponding decision problem Prime-DFA_fin is proven. The paper also characterizes the primality of acyclic DFAs under two different notions of compositionality, union and union-intersection compositionality.
Additionally, the paper introduces the notion of S-primality, where a DFA 𝒜 is S-prime if there do not exist DFAs 𝒜₁,… ,𝒜_t with ℒ(𝒜) = ⋂_{i=1}^t ℒ(𝒜_i) such that each 𝒜_i has strictly less states than 𝒜 itself. It is proven that the problem of deciding S-primality for a given DFA is NL-hard. To do so, the NL-completeness of 2Minimal-DFA, the basic problem of deciding minimality for a DFA with at most two letters, is proven.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Deterministic finite automaton (DFA)
  • Regular languages
  • Finite languages
  • Decomposition
  • Primality
  • Minimality

Metrics

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

Related Versions

References

  1. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008. URL: https://mitpress.mit.edu/9780262026499/principles-of-model-checking/.
  2. Sang Cho and Dung T. Huynh. The parallel complexity of finite-state automata problems. Inf. Comput., 97(1):1-22, 1992. URL: https://doi.org/10.1016/0890-5401(92)90002-W.
  3. Willem P. de Roever, Hans Langmaack, and Amir Pnueli, editors. Compositionality: The Significant Difference, International Symposium, COMPOS'97, Bad Malente, Germany, September 8-12, 1997. Revised Lectures, volume 1536 of Lecture Notes in Computer Science. Springer, 1998. URL: https://doi.org/10.1007/3-540-49213-5.
  4. Henning Fernau and Markus Holzer. Personal communication. Google Scholar
  5. Peter Gazi and Branislav Rovan. Assisted problem solving and decompositions of finite automata. In Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, and Mária Bieliková, editors, SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, volume 4910 of Lecture Notes in Computer Science, pages 292-303. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-77566-9_25.
  6. E. Mark Gold. Complexity of automaton identification from given data. Inf. Control., 37(3):302-320, 1978. URL: https://doi.org/10.1016/S0019-9958(78)90562-4.
  7. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0539-5.
  8. Ismaël Jecker, Orna Kupferman, and Nicolas Mazzocchi. Unary prime languages. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 51:1-51:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.51.
  9. Ismaël Jecker, Nicolas Mazzocchi, and Petra Wolf. Decomposing permutation automata. In Serge Haddad and Daniele Varacca, editors, 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference, volume 203 of LIPIcs, pages 18:1-18:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2021.18.
  10. Orna Kupferman and Jonathan Mosheiff. Prime languages. Inf. Comput., 240:90-107, 2015. URL: https://doi.org/10.1016/j.ic.2014.09.010.
  11. Niklas Lauffer, Beyazit Yalcinkaya, Marcell Vazquez-Chanlatte, Ameesh Shah, and Sanjit A. Seshia. Learning deterministic finite automata decompositions from examples and demonstrations. In Alberto Griggio and Neha Rungta, editors, 22nd Formal Methods in Computer-Aided Design, FMCAD 2022, Trento, Italy, October 17-21, 2022, pages 1-6. IEEE, 2022. URL: https://doi.org/10.34727/2022/isbn.978-3-85448-053-2_39.
  12. Wim Martens, Matthias Niewerth, and Thomas Schwentick. Schema design for XML repositories: complexity and tractability. In Jan Paredaens and Dirk Van Gucht, editors, Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA, pages 239-250. ACM, 2010. URL: https://doi.org/10.1145/1807085.1807117.
  13. Alexandru Mateescu, Arto Salomaa, and Sheng Yu. Factorizations of languages and commutativity conditions. Acta Cybern., 15(3):339-351, 2002. URL: https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3583.
  14. Arto Salomaa and Sheng Yu. On the decomposition of finite languages. In Grzegorz Rozenberg and Wolfgang Thomas, editors, Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6-9 July 1999, pages 22-31. World Scientific, 1999. URL: https://doi.org/10.1142/9789812792464_0003.
  15. Philip Sieder. A lower bound for primality of finite languages. CoRR, abs/1902.06253, 2019. URL: https://arxiv.org/abs/1902.06253.
  16. Stavros Tripakis. Compositionality in the science of system design. Proc. IEEE, 104(5):960-972, 2016. URL: https://doi.org/10.1109/JPROC.2015.2510366.
  17. Moshe Y. Vardi and Pierre Wolper. An automata-theoretic approach to automatic program verification (preliminary report). In Proceedings of the Symposium on Logic in Computer Science (LICS '86), Cambridge, Massachusetts, USA, June 16-18, 1986, pages 332-344. IEEE Computer Society, 1986. URL: https://hdl.handle.net/2268/116609.
  18. Wojciech Wieczorek. An algorithm for the decomposition of finite languages. Log. J. IGPL, 18(3):355-366, 2010. URL: https://doi.org/10.1093/jigpal/jzp032.
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