Back to Search Start Over

Regular Expressions Avoiding Absorbing Patterns and the Significance of Uniform Distribution.

Authors :
Broda, Sabine
Machiavelo, António
Moreira, Nelma
Reis, Rogério
Source :
International Journal of Foundations of Computer Science. Jul2024, p1-18. 18p.
Publication Year :
2024

Abstract

Although regular expressions do not correspond univocally to regular languages, it is still worthwhile to study their properties and algorithms. For the average case analysis one often relies on the uniform random generation using a specific grammar for regular expressions, that can represent regular languages with more or less redundancy. Generators that are uniform on the set of expressions are not necessarily uniform on the set of regular languages. Nevertheless, it is not straightforward that asymptotic estimates obtained by considering the whole set of regular expressions are different from those obtained using a more refined set that avoids some large class of equivalent expressions. In this paper we study a set of expressions that avoid a given absorbing pattern. It is shown that, although this set is significantly smaller than the standard one, the asymptotic average estimates for the size of the Glushkov automaton for these expressions does not differ from the standard case. Furthermore, for this set the asymptotic density of 휀-accepting expressions is also the same as for the set of all standard regular expressions. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
01290541
Database :
Academic Search Index
Journal :
International Journal of Foundations of Computer Science
Publication Type :
Academic Journal
Accession number :
178721693
Full Text :
https://doi.org/10.1142/s0129054124420036