This article is cited in 1 paper

Finite transducers and nondeterministic state complexity of regular languages

G. A. Povarov

Chair of Algebra and Discrete Mathematics, Ural State University, Ekaterinburg, Russia

Abstract: We obtain a sharp upper bound for the nondeterministic state complexity of the application of a finite transducer to a regular language.

Keywords: finite transducer, nondeterministic finite automaton, regular language, descriptive complexity, nondeterministic state complexity.

UDC: 519.713

Received: 25.05.2008

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:6, 19–25

Bibliographic databases:

• 
•