On the Uniform Distribution of Regular Expressions

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2021

Autores

Broda, S (Autor) FCUP; António Machiavelo (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Ata de Conferência Internacional

Título: Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings

Páginas: 13-25

23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021

5 September 2021 through 5 September 2021

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00V-Z16

DOI: 10.1007/978-3-030-93489-7_2

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13