Christoph Koutschan,
"Regular Languages and Their Generating Functions: The Inverse Problem"
, in Theoretical Computer Science, Vol. 391, Nummer 1-2, Seite(n) 65-74, 2008, ISSN: 0304-3975
Original Titel:
Regular Languages and Their Generating Functions: The Inverse Problem
Sprache des Titels:
Englisch
Original Kurzfassung:
The technique of determining a generating function for an unambiguous context-free language is known as the Schuetzenberger 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 N-rationality. In addition, some aspects and problems concerning the implementation are discussed; some examples from combinatorics illustrate its applicability.
Journal = Theoretical Computer Science