LIPIcs.MFCS.2021.63.pdf
- Filesize: 0.99 MB
- 18 pages
Document
The Simplest Non-Regular Deterministic Context-Free Language
Authors
Petr Jančar 
,
-
Part of:
Volume:
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-18
File
Document Identifiers
Author Details
Acknowledgements
J. Šíma also thanks Martin Plátek for his intensive collaboration at the first stages of this research.
Cite AsGet BibTex
Petr Jančar and Jiří Šíma. The Simplest Non-Regular Deterministic Context-Free Language. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 63:1-63:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.63
https://doi.org/10.4230/LIPIcs.MFCS.2021.63
Abstract
We introduce a new notion of 𝒞-simple problems for a class 𝒞 of decision problems (i.e. languages), w.r.t. a particular reduction. A problem is 𝒞-simple if it can be reduced to each problem in 𝒞. This can be viewed as a conceptual counterpart to 𝒞-hard problems to which all problems in 𝒞 reduce. Our concrete example is the class of non-regular deterministic context-free languages (DCFL'), with a truth-table reduction by Mealy machines. The main technical result is a proof that the DCFL' language L_# = {0^n1^n ∣ n ≥ 1} is DCFL'-simple, and can be thus viewed as one of the simplest languages in the class DCFL', in a precise sense. The notion of DCFL'-simple languages is nontrivial: e.g., the language L_R = {wcw^R∣ w ∈ {a,b}^*} is not DCFL'-simple.
By describing an application in the area of neural networks (elaborated in another paper), we demonstrate that 𝒞-simple problems under suitable reductions can provide a tool for expanding the lower-bound results known for single problems to the whole classes of problems.
Subject Classification
ACM Subject Classification
- Theory of computation → Grammars and context-free languages
- Theory of computation → Problems, reductions and completeness
- Theory of computation → Transducers
Keywords
- deterministic context-free language
- truth-table reduction
- Mealy automaton
- pushdown automaton
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- M. Anabtawi, S. Hassan, Christos A. Kapoutsis, and M. Zakzok. An oracle hierarchy for small one-way finite automata. In Proceedings of LATA 2019, LNCS 11417, pages 57-69. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-13435-8_4.
- Jean Berstel and Luc Boasson. Context-free languages. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pages 59-102. Elsevier and MIT Press, 1990. URL: https://doi.org/10.1016/b978-0-444-88074-1.50007-x.
- Sheila A. Greibach. The hardest context-free language. SIAM J. Comput., 2(4):304-310, 1973. URL: https://doi.org/10.1137/0202025.
- John E. Hopcroft and Jeffrey D. Ullman. Formal languages and their relation to automata. Addison-Wesley, 1969. URL: https://www.worldcat.org/oclc/00005012.
- Petr Jančar. Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence. J. Comput. Syst. Sci., 109:22-44, 2020. URL: https://doi.org/10.1016/j.jcss.2019.10.002.
- Petr Jančar, František Mráz, Martin Plátek, and Jörg Vogel. On monotonic automata with a restart operation. J. Autom. Lang. Comb., 4(4):287-311, 1999. URL: https://doi.org/10.25596/jalc-1999-287.
- František Mráz, Dana Pardubská, Martin Plátek, and Jiří Šíma. Pumping deterministic monotone restarting automata and DCFL. In Proceedings of ITAT 2020, CEUR Workshop Proceedings 2718, pages 51-58, 2020. URL: http://ceur-ws.org/Vol-2718/paper13.pdf.
- Klaus Reinhardt. Hierarchies over the context-free languages. In Proceedings of IMYCS 1990, LNCS 464, pages 214-224. Springer, 1990. URL: https://doi.org/10.1007/3-540-53414-8_44.
-
Hava T. Siegelmann. Neural networks and analog computation - Beyond the Turing limit. Birkhäuser, 1999.
- Jiří Šíma. Analog neuron hierarchy. Neural Netw., 128:199-215, 2020. URL: https://doi.org/10.1016/j.neunet.2020.05.006.
- Jiří Šíma. Stronger separation of analog neuron hierarchy by deterministic context-free languages, 2021. (submitted to a journal). URL: http://arxiv.org/abs/2102.01633.
- Jiří Šíma and Pekka Orponen. General-purpose computation with neural networks: A survey of complexity theoretic results. Neural Comput., 15(12):2727-2778, 2003. URL: https://doi.org/10.1162/089976603322518731.
- Jiří Šíma and Martin Plátek. One analog neuron cannot recognize deterministic context-free languages. In Proceedings of ICONIP 2019, Part III, LNCS 11955, pages 77-89. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-36718-3_7.
- Tomoyuki Yamakami. Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages. In Proceedings of SOFSEM 2014, LNCS 8327, pages 514-525. Springer, 2014. (full version https://arxiv.org/abs/1303.1717). URL: https://doi.org/10.1007/978-3-319-04298-5_45.