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

• Type: Article in International Scientific Journal
• Date: 2023

Authors

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

Journal

Title: Theoretical Computer Science

Vol. 956

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: 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/).

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 17