Considering the uniform distribution on sets of m non-empty words whose sum of lengths is n, we establish that the average state complexities of the rational operations are asymptotically linear.
Bassino, F., Giambruno, L., Nicaud, C. (2010). The average state complexity of rational operations on finite languages is linear. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 21, 495-516 [10.1142/S0129054110007398].
The average state complexity of rational operations on finite languages is linear
GIAMBRUNO, Laura;
2010-01-01
Abstract
Considering the uniform distribution on sets of m non-empty words whose sum of lengths is n, we establish that the average state complexities of the rational operations are asymptotically linear.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
