Publication Details

New language operations in formal language theory

MEDUNA, A.; VÍTEK, M. New language operations in formal language theory. Schedae Informaticae, 2004, vol. 2004, no. 13, p. 123-150. ISSN: 0860-0295.

Czech title

Nové jazykové operace v teorii formálních jazyků

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
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 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{BUT45743,
  author="Alexandr {Meduna} and Martin {Vítek}",
  title="New language operations in formal language theory",
  journal="Schedae Informaticae",
  year="2004",
  volume="2004",
  number="13",
  pages="123--150",
  issn="0860-0295"
}