Publication result detail

Insertion and Deletion Operations in Formal Language Theory

VÍTEK, M.

Original Title

Insertion and Deletion Operations in Formal Language Theory

English Title

Insertion and Deletion Operations in Formal Language Theory

Type

Paper in proceedings outside WoS and Scopus

Original 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.

English 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.

Keywords

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

Key words in English

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

Authors

VÍTEK, M.

Released

10.03.2005

Publisher

Marq software s.r.o.

Location

Ostrava

ISBN

80-86840-09-3

Book

Proceedings of 8th Spring International Conference ISIM '05

Pages from

73

Pages to

80

Pages count

8

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",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-09-3"
}