RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2000 Volume 12, Issue 1, Pages 145–157 (Mi dm319)

This article is cited in 1 paper

On the complexity of the realization of finite languages by formulas

E. V. Orlova


Abstract: 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.

UDC: 519.6

Received: 17.01.2000

DOI: 10.4213/dm319


 English version:
Discrete Mathematics and Applications, 2000, 10:2, 159–173

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024