On the Average State Complexity of Partial Derivative Transducers

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

Autores

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

Ata de Conferência Internacional

Título: SOFSEM 2020: THEORY AND PRACTICE OF COMPUTER SCIENCE

Páginas: 174-186

46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)

Limassol, CYPRUS, JAN 20-24, 2020

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 2 Citações

Outras Informações

ID Authenticus: P-00R-P5G

DOI: 10.1007/978-3-030-38919-2_15

Abstract (EN): 2D regular expressions represent rational relations over two alphabets. In this paper we study the average state complexity of partial derivative standard transducers (T-PD) that can be defined for (general) 2D expressions where basic terms are pairs of ordinary regular expressions (1D). While in the worst case the number of states of T-PD can be O(n(2)), where n is the size of the expression, asymptotically and on average that value is bounded from above by O(n(3/2)). Moreover, asymptotically and on average the alphabetic size of a 2D expression is half of the size of that expression. 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.

Idioma: Inglês

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

Nº de páginas: 13