Paper Info
Title
Higher order indexed monadic systems.
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.
Year
DOI
Venue
2011
10.4230/LIPIcs.FSTTCS.2011.469
Leibniz International Proceedings in Informatics
Keywords
Field
DocType
Higher-order indexed languages,monadic systems
Inverse,Discrete mathematics,Indexed language,Automaton,Rewriting,Hierarchy,Monad (functional programming),Mathematics,Monadic predicate calculus
Conference
Volume
ISSN
Citations 
13
1868-8969
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Didier Caucal147039.15
Teodor Knapik222216.13