Regular languages and their generating functions: The inverse problem
详细信息 查看全文
- 作者：Christoph Koutschan
- 关键词：Formal power series ; Regular language ; Soittola’ ; s Theorem ; Integer sequence ; ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4PYP776-7&_mathId=mml2&_user=10&_cdi=5674&_rdoc=9&_a
- 刊名：Theoretical Computer Science
- 出版年：2008
- 出版时间：4 February 2008
- 年：2008
- 卷：391
- 期：1-2
- 页码：65-74
- 全文大小：271 K
文摘
The technique of determining a generating function for an unambiguous context-free language is known as the Schützenberger 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 -rationality. In addition, some aspects and problems concerning the implementation are discussed; some examples from combinatorics illustrate its applicability.