License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2021.5
URN: urn:nbn:de:0030-drops-142439
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14243/
Go to the corresponding LIPIcs Volume Portal

Simonsen, Jakob Grue

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

pdf-format:
LIPIcs-FSCD-2021-5.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{simonsen:LIPIcs.FSCD.2021.5,
  author =	{Simonsen, Jakob Grue},
  title =	{{The Expressive Power of One Variable Used Once: The Chomsky Hierarchy and First-Order Monadic Constructor Rewriting}},
  booktitle =	{6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-191-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{195},
  editor =	{Kobayashi, Naoki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14243},
  URN =		{urn:nbn:de:0030-drops-142439},
  doi =		{10.4230/LIPIcs.FSCD.2021.5},
  annote =	{Keywords: Constructor term rewriting, Chomsky Hierarchy, Implicit Complexity}
}

Keywords: Constructor term rewriting, Chomsky Hierarchy, Implicit Complexity
Collection: 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)
Issue Date: 2021
Date of publication: 06.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI