Block Substitutions and Their Properties

• Autorzy: Kari L. , Losseva E.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

formal languages; Chomshy hierarchy; block substitution

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 165--178
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Kari L.

autor

Losseva E.

• Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada,

Bibliografia

• [1] J. Berstel, D. Perrin: Theory of Codes. Academic Press, Orlando, 1985.
• [2] J.H. Conway: Regular Algebra and Finite Machines. Chapman and Hall, London, 1971.
• [3] M. Crochemore, C. Hancart: Automata for matching patterns. In[15], vol. II, 399-462.
• [4] T. Head, A.Weber: Deciding code related properties by means of finite transducers. In Sequences II,Methods in Communication, Security, and Computer Science (R. Capocelli, A. de Santis, U. Vaccaro, eds.), Springer-Verlag, Berlin, 1993, 260-272.
• [5] H. Jürgensen, S. Konstantinidis: Codes. In [15], vol. I, 511-607.
• [6] H. Jürgensen, K. Salomaa, S. Yu: Transducers and the decidability of independence in free monoids. Theoretical Computer Science, 134 (1994), 107-117.
• [7] L. Kari: On Insertion and Deletion in formal languages. PhD thesis, University of Turku, Finland, 1991.
• [8] L. Kari: On language equations with invertible operations. Theoretical Computer Science, 132 (1994), 129-150.
• [9] L. Kari, S. Konstantinidis: Language equations, maximality and error-detection. Elsevier Science, 2004.
• [10] L. Kari, G. Thierrin: K-catenation and applications: k-prefix codes. Journal of Information and Optimization Sciences, 16 (1995), 263-276.
• [11] L. Kari, G. Thierrin: Maximal and minimal solutions to language equations. Journal of Computer and System Sciences, 53 (1996), 487-496.
• [12] S. Konstantinidis: Relationships between different error-correcting capabilities of a code. IEEE Trans. Inform. Theory, 47 (2001), 2065-2069.
• [13] S. Konstantinidis: Transducers and the properties of error-detection, error-correction, and finite-delay decodability. J. Universal Comp. Science, 8 (2002), 278-291.
• [14] S. Konstantinidis, A. O'Hearn: Error-detecting properties of languages. Theoretical Computer Science, 276 (2002), 355-375.
• [15] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.
• [16] A. Salomaa: Formal Languages. Academic Press, New York, 1973.
• [17] H.J. Shyr: Free monoids and languages. Institute of AppliedMathematics, National Chung-Hsing University, Taichung, Taiwan, 1991.
• [18] S. Yu: Regular Languages. In [15], vol. I, 41-110.