DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.469

Higher order indexed monadic systems

Authors: Didier Caucal and Teodor Knapik

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

A word rewriting system is called monadic if each of its right hand sides is either a single letter or the empty word. We study the images of higher order indexed languages (defined by Maslov) under inverse derivations of infinite monadic systems. We show that the inverse derivations of deterministic level n indexed languages by confluent regular monadic systems are deterministic level n+1 languages, and that the inverse derivations of level n indexed monadic systems preserve level $n$ indexed languages. Both results are established using a fine structural study of classes of infinite automata accepting level $n$ indexed languages. Our work generalizes formerly known results about regular and context-free languages which form the first two levels of the indexed language hierarchy.

Cite as

Didier Caucal and Teodor Knapik. Higher order indexed monadic systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 469-480, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{caucal_et_al:LIPIcs.FSTTCS.2011.469,
  author =	{Caucal, Didier and Knapik, Teodor},
  title =	{{Higher order indexed monadic systems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{469--480},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.469},
  URN =		{urn:nbn:de:0030-drops-33379},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.469},
  annote =	{Keywords: Higher-order indexed languages, monadic systems}
}

Search Results

Documents authored by Knapik, Teodor

Higher order indexed monadic systems

Abstract

Cite as

Thanks for your feedback!

Could not send message