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

Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
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 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"
}