Publication Details

Insertion and Deletion Operations in Formal Language Theory

VÍTEK Martin. Insertion and Deletion Operations in Formal Language Theory. In: Proceedings of 8th Spring International Conference ISIM '05. Ostrava, 2005, pp. 73-80. ISBN 80-86840-09-3.

Czech title

Vkládací a mazací operace v teorii formálních jazyků

Type

conference paper

Language

english

Authors

Vítek Martin, Ing., Ph.D. (DIFS FIT BUT)

Keywords

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

Abstract

Stringology is a modern part of the formal language theory which deals with strings and operations on them. These operations we can divide into two groups - insertion and deletion operations. This paper presents these operations and studies their closure properties. The main contribution of this paper are algorithms constructing finite automata accepting the result of these operations from finite automata accepting the operands. By designing these algorithms we demonstrate, that the family of regular languages is closed under these operations.

Published

2005

Pages

73-80

Proceedings

Proceedings of 8th Spring International Conference ISIM '05

Conference

8th International Conference on Information Systems Implementation and Modelling, Hradec nad Moravicí, CZ

ISBN

80-86840-09-3

Place

Ostrava, CZ

BibTeX

@INPROCEEDINGS{FITPUB7729,
   author = "Martin V\'{i}tek",
   title = "Insertion and Deletion Operations in Formal Language Theory",
   pages = "73--80",
   booktitle = "Proceedings of 8th Spring International Conference ISIM '05",
   year = 2005,
   location = "Ostrava, CZ",
   ISBN = "80-86840-09-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7729"
}