Higher order indexed monadic systems

Didier Caucal & Teodor Knapik
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...