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

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Vítek Martin, Ing., Ph.D., FIT (FIT), DIFS (FIT)

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.

Keywords

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

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"
}

Projects

Optimally Integrated Models of Modern Information Technologies, GACR, Standardní projekty, GA201/04/0441, start: 2004-01-01, end: 2006-12-31, completed

Departments

Department of Information Systems (DIFS)