Geodesic
Finite transducers and nondeterministic state complexity of regular languages
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2010), pp. 23-31.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{IVM_2010_6_a2,
     author = {G. A. Povarov},
     title = {Finite transducers and nondeterministic state complexity of regular languages},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {23--31},
     publisher = {mathdoc},
     number = {6},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2010_6_a2/}
}
TY  - JOUR
AU  - G. A. Povarov
TI  - Finite transducers and nondeterministic state complexity of regular languages
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2010
SP  - 23
EP  - 31
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2010_6_a2/
LA  - ru
ID  - IVM_2010_6_a2
ER  - 
%0 Journal Article
%A G. A. Povarov
%T Finite transducers and nondeterministic state complexity of regular languages
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2010
%P 23-31
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2010_6_a2/
%G ru
%F IVM_2010_6_a2
G. A. Povarov. Finite transducers and nondeterministic state complexity of regular languages. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2010), pp. 23-31. http://geodesic.mathdoc.fr/item/IVM_2010_6_a2/

[1] Birget J.-C., “Intersection and union of regular languages and state complexity”, Inform. Proc. Lett., 43:4 (1992), 185–190 | DOI | MR | Zbl

[2] Gruber H., Holzer M., “Finding lower bounds for nondeterministic state complexity is hard”, Lect. Notes Comput. Sci., 4036, Springer, Berlin, 2006, 363–374 | MR | Zbl

[3] Kutrib M., Holzer M., “Unary language operations and their nondeterministic state complexity”, Lect. Notes Comput. Sci., 2450, Springer, Berlin, 2003, 162–172 | MR | Zbl

[4] Salomaa K., “Descriptional complexity of nondeterministic finite automata”, Lect. Notes Comput. Sci., 4588, Springer, Berlin, 2007, 31–35 | MR | Zbl

[5] Kutrib M., Holzer M., “State complexity of basic operations on nondeterministic finite automata”, Lect. Notes Comput. Sci., 2608, Springer, Berlin, 2003, 148–157 | MR | Zbl

[6] Yu S., “Regular languages”, Handbook of Formal Languages, V. 1, Springer, N.-Y., 1997, 41–110 | MR | Zbl

[7] Hopcroft J. E., Motwani R., Ullman J. D., Introduction to automata theory, languages and computation, Addison-Wesley, MA, 2001, 521 pp. | MR | Zbl

[8] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985, 320 pp. | MR | Zbl

[9] Sakarovitch J., Éléments de théorie des automates, Vuibert Informatique, Paris, 2003, 816 pp. | Zbl

[10] Calude C., Salomaa K., Yu S., “Metric lexical analysis”, Lect. Notes Comput. Sci., 2214, Springer, Berlin, 2001, 48–59 | Zbl

[11] Karhumäki J., Automata and formal languages, , 2007 http://www.math.utu.fi/en/home/karhumak/Automata2007.pdf

[12] Povarov G., Proc. of Language and Automata Theory and Applications Conference, Universitat Rovira i Virgili, Tarragona, 2007