Publication Details

New language operations in formal language theory

MEDUNA Alexander and VÍTEK Martin. New language operations in formal language theory. Schedae Informaticae, vol. 2004, no. 13, pp. 123-150. ISSN 0860-0295.
Czech title
Nové jazykové operace v teorii formálních jazyků
Type
journal article
Language
english
Authors
Keywords
  • stringology
  • sequential insertion
  • parallel insertion
  • scattered sequential insertion
  • sequential deletion
  • parallel deletion
  • scattered sequential deletion
  • finite automata
  • closure properties
Abstract

Stringology represents a modern part of the formal language theory, which deals with strings, languages and operations on them. It introduces many new language operations, which can be divided into two groups - insertion and deletion operations. This paper presents these operations and some 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.

Published
2004
Pages
123-150
Journal
Schedae Informaticae, vol. 2004, no. 13, ISSN 0860-0295
BibTeX
@ARTICLE{FITPUB7460,
   author = "Alexander Meduna and Martin V\'{i}tek",
   title = "New language operations in formal language theory",
   pages = "123--150",
   journal = "Schedae Informaticae",
   volume = 2004,
   number = 13,
   year = 2004,
   ISSN = "0860-0295",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7460"
}
Back to top