2026-07-20T05:38:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3337 2024-03-06T10:34:08Z ddc:004 open_access

Higher order indexed monadic systems Caucal, Didier Knapik, Teodor Higher-order indexed languages monadic systems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Didier Caucal and Teodor Knapik 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.469 urn:nbn:de:0030-drops-33379 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.469 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode