On the average complexity of partial derivative transducers *,**,***

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

Autores

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

Revista

Título: Theoretical Computer Science

Vol. 956

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00Y-3E6

DOI: 10.1016/j.tcs.2023.113830

Abstract (EN): 2D regular expressions represent rational relations over two alphabets sigma and A. In standard 2D expressions (S2D-RE) the basic terms are generators of sigma* x A*, while in generalised 2D expressions (2D-RE) the basic terms are pairs of (ordinary) regular expressions over one alphabet (1D). In this paper we study the average state complexity of partial derivative standard transducers (TPD) for both S2D-RE and 2D-RE. For S2D-RE we obtain the same asymptotic bounds as for partial derivative automata. For 2D-RE, while in the worst case the number of states of TPD can be O (n2), where n is the size of the expression, asymptotically and on average that value is bounded from above by O (n 2 ). We also show that asymptotically and on average the alphabetic size of a 2D-RE is half of its size. All results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. In particular, we generalise the methods developed in previous work to a broad class of analytic functions.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Idioma: Inglês

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

Nº de páginas: 17