EDT0L grammars with only one variable have tractable generating functions

Department of Mathematics, Southern Utah University, Cedar City, 84720, UT, USA

^* Corresponding author: freden@suu.edu

Received: 21 December 2022
Accepted: 8 June 2023

Abstract

We introduce new counting techniques for computing the growth of EDT0L languages based on generalized Parikh vectors. The structure generating function S(z) for any language formed from an unambiguous EDT0L system with one variable and m tables is tractable in the sense that its Taylor polynomial S_N(z) can be constructed in time O(N^2+log₂m). We illustrate by example that this result is not necessarily true for systems with several variables. The dichotomy between one variable and several variables is partially explained using matrix algebra.