Regular languages and their generating functions: The inverse problem. The technique of determining a generating function for an unambiguous context-free language is known as the Sch”utzenberger methodology. For regular languages, Elena Barcucci et al. proposed an approach for inverting this methodology based on Soittola’s theorem. This idea allows a combinatorial interpretation (by means of a regular language) of certain positive integer sequences that are defined by C-finite recurrences. In this paper we present a Maple implementation of this inverse methodology and describe various applications. We give a short introduction to the underlying theory, i.e., the question of deciding $mathbb N$-rationality. In addition, some aspects and problems concerning the implementation are discussed; some examples from combinatorics illustrate its applicability.
Keywords for this software
References in zbMATH (referenced in 7 articles , 1 standard article )
Showing results 1 to 7 of 7.
- Bilotta, S.; Pergola, E.; Pinzani, R.; Rinaldi, S.: Recurrence relations, succession rules and the positivity problem (2019)
- Banderier, Cyril; Drmota, Michael: Formulae and asymptotics for coefficients of algebraic functions (2015)
- Banderier, Cyril; Drmota, Michael: Coefficients of algebraic functions: formulae and asymptotics (2013)
- Lavallée, Sylvain: Characteristic polynomials of nonnegative real square matrices and generalized clique polynomials (2010)
- Berstel, Jean; Reutenauer, Christophe: Another proof of Soittola’s theorem (2008)
- Koutschan, Christoph: Regular languages and their generating functions: The inverse problem (2008)
- Lavallée, Sylvain: (\mathbbZ)-rationality of a certain class of formal series (2008)