On the Average State Complexity of Partial Derivative Transducers

• Type: Article in International Conference Proceedings Book
• Date: 2020

Authors

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

Conference proceedings International

Title: SOFSEM 2020: THEORY AND PRACTICE OF COMPUTER SCIENCE

Pages: 174-186

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

Limassol, CYPRUS, JAN 20-24, 2020

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 2 Citations

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13