Acta Cybernetica 2017/2. [antikvár]

Acta Cybernetica 23 (2018) 981-993.On Derivation Languages of a Class of Splicing SystemsKalpana Mahalingam^ Prithwineel Paul^ and Erkki MakinencAbstractDerivation languages are language theoretical tools that describe halting derivation processes of a generating device. We consider two types of derivation languages, namely Szilard and control languages for splicing systems where iterated splicing is done in non-uniform way defined by Mitrana, Petre and Rogojin in 2010. The families of Szilard (rules and labels are mapped in a one to one manner) and control (more than one rule can share the same label) languages generated by splicing systems of this type are then compared with the family of languages in the Chomsky hierarchy. We show that context-free languages can be generated as Szilard and control languages and any non-empty context-free language is a morphic image of the Szilard language of this type of system with finite set of rules and axioms. Moreover, we show that these systems with finite set of axioms and regular set of rules are capable of generating any recursively enumerable language as a control language.Keywords: Splicing systems, Szilard languages, Control languages1 IntroductionThe information regarding terminal derivation processes of a generative device is well studied in the literature. Each rule of the generative system in question is labeled and the given sequence of labels is considered as the output of the computation. The set of all such words constitute a language. When the labelling is done in a one to one fashion, the set of all labeled sequences is called a Szilard language. Szilard languages have been defined for a variety of generative mechanisms (for Chomsky grammars [8, 9, 14, 12], for regulated rewritings [5, 18] and for grammar systems [6, 10], to name a few) and their closure and decidability properties andCorresponding authorb Department of Mat hematics,Indian Institute of Technology, Madras, Chennai - 36. E-mail: kmahalingamOiitm.ac.in, prithwineelpaulQgmail.comcFaculty of Natural Sciences/Computer Science, University of Tampere, Finland. E-mail: emQsis.uta.fiDOI: 10.14232/actacyb.23.4.2018.1