Average Complexity of Partial Derivatives for Synchronised Shuffle Expressions

• Tipo: Artigo em Revista Científica Internacional
• Data: 2023

Autores

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

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00Y-T7W

DOI: 10.1007/978-3-031-40247-0_7

Abstract (EN): Synchronised shuffle operators allow to specify symbols on which the operands must or can synchronise instead of interleave. Recently, partial derivative and position based automata for regular expressions with synchronised shuffle operators were introduced. In this paper, using the framework of analytic combinatorics, we study the asymptotic average state complexity of partial derivative automata for regular expressions with strongly and arbitrarily synchronised shuffles. The new results extend and improve the ones previously obtained for regular expressions with shuffle and intersection. For intersection, asymptotically the average state complexity of the partial derivative automaton is 3, which significantly improves the known exponential upper-bound. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Idioma: Inglês

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

Nº de páginas: 12