Block Substitutions and Their Properties

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Kari, Lila | Losseva, Elena

Affiliations: Department of Computer Science The University of Western Ontario London, ON, Canada, N6A 5B7. E-mail: {lila,elena}@csd.uwo.ca

Abstract: We introduce a type of substitution operation inspired by errors occurring in biologically encoded information. We derive the closure properties of language families in the Chomsky hierarchy under these substitution operations. Moreover, we consider some language equations involving these operations and investigate decidability of the existence of solutions to such equations.

Keywords: Formal languages, Chomshy hierarchy, block substitution

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 165-178, 2006