Geodesic
On the complexity of the realization of finite languages by formulas
Diskretnaya Matematika, Tome 12 (2000) no. 1, pp. 145-157.

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

We consider realizations of finite languages of regular expressions over finite alphabets by formulas with minimal complexity. Some classes of languages are investigated and for their complexities the best bounds up to the order are obtained. The main attention is given to realizations of languages consisting of words of equal length. 
@article{DM_2000_12_1_a11,
     author = {E. V. Orlova},
     title = {On the complexity of the realization of finite languages by formulas},
     journal = {Diskretnaya Matematika},
     pages = {145--157},
     publisher = {mathdoc},
     volume = {12},
     number = {1},
     year = {2000},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_1_a11/}
}
TY  - JOUR
AU  - E. V. Orlova
TI  - On the complexity of the realization of finite languages by formulas
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 145
EP  - 157
VL  - 12
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_1_a11/
LA  - ru
ID  - DM_2000_12_1_a11
ER  - 
%0 Journal Article
%A E. V. Orlova
%T On the complexity of the realization of finite languages by formulas
%J Diskretnaya Matematika
%D 2000
%P 145-157
%V 12
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2000_12_1_a11/
%G ru
%F DM_2000_12_1_a11
E. V. Orlova. On the complexity of the realization of finite languages by formulas. Diskretnaya Matematika, Tome 12 (2000) no. 1, pp. 145-157. http://geodesic.mathdoc.fr/item/DM_2000_12_1_a11/

[1] Glushkov V. M., Sintez tsifrovykh avtomatov, Fizmatgiz, Moskva, 1962

[2] Klini S. K., “Predstavlenie sobytii v nervnykh setyakh i konechnykh avtomatakh”, Avtomaty, IL, Moskva, 1956, 15–67

[3] Lupanov O. B., “O realizatsii funktsii algebry logiki formulami iz konechnykh klassov (formulami ogranichennoi glubiny) v bazise $\$, $\vee$, $\neg$”, Problemy kibernetiki, 6 (1961), 5–14 | MR | Zbl

[4] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10 (1963), 88–96 | MR

[5] Orlova E.,V., Tezisy dokladov 11-i mezhdunarodnoi konferentsii po problemam teoreticheskoi kibernetiki, RGGU, Moskva, 1996

[6] Orlova E. V., “O slozhnosti regulyarnykh vyrazhenii dlya funktsii iz nekotorykh klassov”, Tezisy dokladov 12-i mezhdunarodnoi konferentsii po problemam teoreticheskoi kibernetiki, Izd-vo mekh.-mat., f-ta MGU, Moskva, 1999

[7] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1979 | MR | Zbl