Back to Search Start Over

THE AVERAGE STATE COMPLEXITY OF RATIONAL OPERATIONS ON FINITE LANGUAGES.

Authors :
Bassino, Frédérique
Giambruno, Laura
Nicaud, Cyril
Source :
International Journal of Foundations of Computer Science. Aug2010, Vol. 21 Issue 4, p495-516. 22p. 1 Diagram.
Publication Year :
2010

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. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*FINITE element method
*SET theory
*COMPUTATIONAL complexity
*UNIFORM distribution (Probability theory)
*ASYMPTOTIC distribution
*LINEAR statistical models

Details

Language :
English
ISSN :
01290541
Volume :
21
Issue :
4
Database :
Academic Search Index
Journal :
International Journal of Foundations of Computer Science
Publication Type :
Academic Journal
Accession number :
52816686
Full Text :
https://doi.org/10.1142/S0129054110007398
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details