From indexed grammars to generating functions

DOI10.1051/ITA/2013041MaRDI QIDQ5397722zbMATH OpenOpenAlexFDO

Authors Jared Adams, Eric Freden, Marni Mishna

Publication date 24 February 2014

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.1779

zbMATH Keywords

DSV methodfunctional equationsgenerating functionsindexed grammars

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15)

Abstract: We extend the Chomsky/Sch"utzenberger method of computing the growth series of an unambiguous context-free language to the larger class of indexed languages. We illustrate the technique with numerous examples.

Recommendations

• Context-free grammars, generating functions and combinatorial arrays
• A class of functions computable by index grammars
• scientific article; zbMATH DE number 3483585
• scientific article; zbMATH DE number 569757
• scientific article; zbMATH DE number 4116001
• scientific article; zbMATH DE number 23840
• A descriptive characterisation of indexed grammars
• HOLONOMIC GENERATING FUNCTIONS AND CONTEXT FREE LANGUAGES

Cited in

(5)

• Rational indexes of generators of the cone of context-free languages
• scientific article; zbMATH DE number 3483585 (Why is no real title available?)
• EDT0L grammars with only one variable have tractable generating functions
• Abstract interpretation of indexed grammars
• On the ET0L subgroup membership problem in bounded automata groups

This page was built for publication: From indexed grammars to generating functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5397722)