New Language Operations in Formal Language Theory

• Autorzy: Meduna A. , Vítek M.
• Języki publikacji: EN

Abstrakty

EN

Stringology represents a modern part of the formal language theory which deal with strings, languages and operations on them. It introduces many new languages operations, which can be divided into two groups - insertion and deletion operations. Some of these operations are described in [1] . This paper presents these operations and some of their properties. Especially, closure properties are studied here. New algorithms that construct finite automata accepting languages resulting from some of these operations are described here. We actually demonstrate by designing these algorithms, that the family of regular languages is closed under these operations.

Słowa kluczowe

EN

stringology; sequential insertion; parallel insertion; scattered sequential insertion; sequential deletion; parallel deletion; scattered sequential deletion; finite automata; closure properties

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2004
• Tom: Vol. 13
• Strony: 123--150
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Meduna A.

• Department of Information Systems, Faculty of Information Technology, Brno, University of Technology, Božetěchova 2, Brno, 612 66, Czech Republic

autor

Vítek M.

• Department of Information Systems, Faculty of Information Technology, Brno, University of Technology, Božetěchova 2, Brno, 612 66, Czech Republic

Bibliografia

• [1]Kari L.; On insertion and deletion in formal languages, PhD thesis, University of Turku, Finland, Department of Mathematics, 1991.
• |2]Amos M.; DNA computation, PhD thesis, University of Warwick, 1997.
• [3]Crochemore M. and Rytter W.; Text algorithms, Oxford University Press, Oxford 1994.
• [4]Greibach S. A. and Hopcroft J. E.; Scattered Context Grammars, J. Comput. Syst. Sci. 3, pp. 232-247, 1969.
• [5]Kari L.; Power of Controlled Insertion and Deletion, LNCS 812, Springer, Berlin 1994.
• [6]Meduna A.; Syntactic Complexity of Scattered Context Productions, Acta Informatica 32, pp. 285-298, 1995.
• [7]Meduna A.; Automata and Languages: Theory and Applications, Springer, London 2000.
• [8]Seberry J. and Pieprzyk J.; Cryptography: An introduction to computer security, Prentice Hall, New York 1989.