Document Open Access Logo

The Expressive Power of One Variable Used Once: The Chomsky Hierarchy and First-Order Monadic Constructor Rewriting

Author Jakob Grue Simonsen

PDF
Thumbnail PDF

File

LIPIcs.FSCD.2021.5.pdf
  • Filesize: 0.67 MB
  • 17 pages

Document Identifiers

Author Details

Jakob Grue Simonsen
  • Department of Computer Science, University of Copenhagen, Denmark

Acknowledgements

I wish to thank the anonymous referees for diligent comments that have helped improve the presentation of the paper.

Cite AsGet BibTex

Jakob Grue Simonsen. The Expressive Power of One Variable Used Once: The Chomsky Hierarchy and First-Order Monadic Constructor Rewriting. In 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 195, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSCD.2021.5

Abstract

We study the implicit computational complexity of constructor term rewriting systems where every function and constructor symbol is unary or nullary. Surprisingly, adding simple and natural constraints to rule formation yields classes of systems that accept exactly the four classes of languages in the Chomsky hierarchy.

Subject Classification

ACM Subject Classification
  • Theory of computation → Grammars and context-free languages
  • Theory of computation → Equational logic and rewriting
  • Theory of computation → Computability
Keywords
  • Constructor term rewriting
  • Chomsky Hierarchy
  • Implicit Complexity

Metrics

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

References

  1. R. Alur and P. Madhusudan. Visibly pushdown languages. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 202-211. ACM, 2004. Google Scholar
  2. M. Avanzini, N. Eguchi, and G. Moser. A path order for rewrite systems that compute exponential time functions. In Manfred Schmidt-Schauß, editor, Proceedings of the 22nd International Conference on Rewriting Techniques and Applications, RTA 2011, volume 10 of LIPIcs, pages 123-138. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011. Google Scholar
  3. M. Avanzini, G. Moser, and A. Schnabl. Automated implicit computational complexity analysis. In Proceedings of the 4th International Joint Conference on Automated Reasoning (IJCAR '08), volume 5195 of Lecture Notes in Computer Science, pages 132-138. Springer-Verlag, 2008. Google Scholar
  4. S. Bellantoni and S.A. Cook. A new recursion-theoretic characterization of the polytime functions. Computational Complexity, 2:97-110, 1992. Google Scholar
  5. Guillaume Bonfante. Some programming languages for logspace and ptime. In Michael Johnson and Varmo Vene, editors, Algebraic Methodology and Software Technology, 11th International Conference, AMAST 2006, Kuressaare, Estonia, July 5-8, 2006, Proceedings, volume 4019 of Lecture Notes in Computer Science, pages 66-80. Springer, 2006. Google Scholar
  6. A.-C. Caron. Linear bounded automata and rewrite systems: Influence of initial configurations on decision properties. In Samson Abramsky and T. S. E. Maibaum, editors, TAPSOFT, Vol.1, volume 493 of Lecture Notes in Computer Science, pages 74-89. Springer, 1991. URL: https://doi.org/10.1007/3-540-53982-4_5.
  7. N. Chomsky. On certain formal properties of grammars. Information and Control, 2(2):137-167, 1959. Google Scholar
  8. L. Czajka. Term rewriting characterisation of LOGSPACE for finite and infinite data. In Hélène Kirchner, editor, 3rd International Conference on Formal Structures for Computation and Deduction, FSCD 2018, July 9-12, 2018, Oxford, UK, volume 108 of LIPIcs, pages 13:1-13:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  9. D. de Carvalho and J. G. Simonsen. An implicit characterization of the polynomial-time decidable sets by cons-free rewriting. In G. Dowek, editor, Rewriting and Typed Lambda Calculi - Joint International Conference, RTA-TLCA 2014, volume 8560 of Lecture Notes in Computer Science, pages 179-193. Springer, 2014. Google Scholar
  10. E. P. Friedman. Equivalence problems for deterministic context-free languages and monadic recursion schemes. Journal of Computer and Systems Sciences, 14(3):344-359, 1977. Google Scholar
  11. E. P. Friedman. Simple context-free languages and free monadic recursion schemes. Mathematical Systems Theory, 11(1):9-28, 1977. Google Scholar
  12. E. P. Friedman and Sheila A. Greibach. Monadic recursion schemes: The effect of constants. Journal of Computer and Systems Sciences, 18(3):254-266, 1979. Google Scholar
  13. J. Goldstine, J. K. Price, and D. Wotschke. On reducing the number of states in a pda. Mathematical Systems Theory, 15(4):315-321, 1982. Google Scholar
  14. S. A. Greibach. Theory of Program Structures: Schemes, Semantics, Verification, volume 36 of Lecture Notes in Computer Science. Springer-Verlag, 1975. Google Scholar
  15. J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education International Inc., 2 edition, 2003. Google Scholar
  16. G. Huet and D.S. Lankford. On the uniform halting problem for term rewriting systems. Rapport Laboria 283, IRIA, 1978. Google Scholar
  17. N. D. Jones. Computability and Complexity from a Programming Perspective. The MIT Press, 1997. Google Scholar
  18. N.D. Jones. The expressive power of higher-order types, or: Life without cons. Journal of Functional Programming, 11(1):55-94, 2001. Google Scholar
  19. C. Kop and J. G. Simonsen. Complexity hierarchies and higher-order cons-free term rewriting. Log. Methods Comput. Sci., 13(3), 2017. Google Scholar
  20. S. Kuroda. Classes of languages and linear-bounded automata. Information and Control, 7(2):207-223, 1964. Google Scholar
  21. H.R. Lewis and C.H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1981. Google Scholar
  22. J.-Y. Marion. Analysing the implicit complexity of programs. Information and Computation, 183(1):2-18, 2003. Google Scholar
  23. M. L. Minsky. Recursive unsolvability of Post’s problem of "tag" and other topics in theory of Turing machines. The Annals of Mathematics, 74(3):437-455, 1961. Google Scholar
  24. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  25. E. Rich. Automata, Computability and Complexity: Theory and Applications. Pearson Prentice Hall, 2008. Google Scholar
  26. M. Sipser. Introduction to the Theory of Computation. Thomson Course Technology, 2nd edition, 2006. Google Scholar
  27. Terese, editor. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2003. Google Scholar
  28. R. Thiemann, H. Zantema, J. Giesl, and P. Schneider-Kamp. Adding constants to string rewriting. Appl. Algebra Eng. Commun. Comput., 19(1):27-38, 2008. URL: https://doi.org/10.1007/s00200-008-0060-6.
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