Publication Details

Insertion and Deletion Operations in Formal Language Theory

VÍTEK, M. Insertion and Deletion Operations in Formal Language Theory. In Proceedings of 8th Spring International Conference ISIM '05. Ostrava: 2005. p. 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.

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

ISBN

80-86840-09-3

Place

Ostrava

BibTeX

@inproceedings{BUT21457,
  author="Martin {Vítek}",
  title="Insertion and Deletion Operations in Formal Language Theory",
  booktitle="Proceedings of 8th Spring International Conference ISIM '05",
  year="2005",
  pages="73--80",
  address="Ostrava",
  isbn="80-86840-09-3"
}