Projects top banner

On the Average State Complexity of Partial Derivative Transducers

SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20-24, 2020, Proceedings

Conference Paper

2D regular expressions represent rational relations over two alphabets. In this paper we study the average state complexity of partial derivative standard transducers ) 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 can be, where n is the size of the expression, asymptotically and on average that value is bounded from above by. 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. © 2020, Springer Nature Switzerland AG.


Year of publication: 2020


ISSN: 0302-9743

Other: dblp:conf/sofsem/KonstantinidisM20


Alternative Titles