Analytic models and ambiguity of context-free languages
From MaRDI portal
Publication:1088414
DOI10.1016/0304-3975(87)90011-9zbMath0612.68069OpenAlexW1997965066MaRDI QIDQ1088414
Publication date: 1987
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/inria-00076071/file/RR-0483.pdf
analytic functionsalgebraic functionscounting generating functionsgeneral density theorem for unambiguous context-free languagestranscendental behaviour
Related Items (77)
Self-avoiding walks and multiple context-free languages ⋮ Holonomic functions and their relation to linearly constrained languages ⋮ Asymptotic approximation by regular languages ⋮ Bounded languages described by GF(2)-grammars ⋮ Walks confined in a quadrant are not always D-finite ⋮ Random palindromes: Multivariate generating function and Bernoulli density ⋮ On the context-freeness of the set of words containing overlaps ⋮ Counting coloured planar maps ⋮ On the language of primitive words ⋮ Thin and slender languages ⋮ Permutations with exactly one copy of a monotone pattern of length \(k\), and a generalization ⋮ Prefixes of infinite words and ambiguous context-free languages ⋮ On the conjecture \(\mathcal {L}_{\mathsf {DFCM}}\subsetneq \mathsf {RCM}\) ⋮ Random generation of finite Sturmian words ⋮ Information rate of some classes of non-regular languages: an automata-theoretic approach ⋮ Rational transductions and complexity of counting problems ⋮ Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy ⋮ Enumerating Davenport-Schinzel sequences ⋮ On the complexity of the cogrowth sequence ⋮ Properties of infinite words : Recent results ⋮ Non-D-finite excursions in the quarter plane ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Rational transductions and complexity of counting problems ⋮ Non-closure under complementation for unambiguous linear grammars ⋮ Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages1 1Work supported by the Grants-in Aid for Scientific Research No. 1 0440034, Japan Society for the Promotion of Sciences and the Dirección General de Enseñanza Superior e Investigación Cientifica, SB 97-00110508 ⋮ The conjugacy growth of the soluble Baumslag-Solitar groups ⋮ On counting functions and slenderness of languages ⋮ The generating function of Kreweras walks with interacting boundaries is not algebraic ⋮ Counting conjugacy classes in groups with contracting elements ⋮ Ambiguity in omega context free languages ⋮ On the Commutative Equivalence of Algebraic Formal Series and Languages ⋮ On universally easy classes for NP-complete problems. ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Sur les facteurs des suites de Sturm. (On the factors of the Sturmian sequences.) ⋮ Counting problems and algebraic formal power series in noncommuting variables ⋮ On the \(q\)-analogue of Pólya's theorem ⋮ Queues, stacks, and transcendentality at the transition to chaos ⋮ On bounded linear codes and the commutative equivalence ⋮ Automatic average-case analysis of algorithms ⋮ On the tiling system recognizability of various classes of convex polyominoes ⋮ On the commutative equivalence of bounded context-free and regular languages: the code case ⋮ The complexity of computing the number of strings of given length in context-free languages ⋮ A decision method for Parikh slenderness of context-free languages ⋮ On 3-dimensional lattice walks confined to the positive octant ⋮ Congruences modulo cyclotomic polynomials and algebraic independence for \(q\)-series ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ On generating series of finitely presented operads ⋮ The cogrowth series for BS(N, N) is D-finite ⋮ On the commutative equivalence of bounded context-free and regular languages: the semi-linear case ⋮ A Revision of Coding Theory for Learning from Language ⋮ On the structure of the counting function of sparse context-free languages. ⋮ The growth function of context-free languages ⋮ On Parikh slender context-free languages ⋮ Walks in the quarter plane: Kreweras' algebraic model ⋮ Counting colored planar maps: algebraicity results ⋮ Walks on the slit plane: Other approaches ⋮ On a class of languages with holonomic generating functions ⋮ Hypergeometric expressions for generating functions of walks with small steps in the quarter plane ⋮ Analytic analysis of algorithms ⋮ Counting walks with large steps in an orthant ⋮ Classifying lattice walks restricted to the quarter plane ⋮ Square lattice walks avoiding a quadrant ⋮ The generating function of planar Eulerian orientations ⋮ ON THE DENSITY OF REGULAR AND CONTEXT-FREE LANGUAGES ⋮ Transcendence of binomial and Lucas' formal power series ⋮ Quantum automata and quantum grammars ⋮ On Hadamard square roots of unity ⋮ The Parikh counting functions of sparse context-free languages are quasi-polynomials ⋮ Why Are So Many Problems Unsolved? ⋮ An example of an indexed language of intermediate growth ⋮ Transcendence of formal power series with rational coefficients ⋮ Random subgroups of Thompson's group \(F\). ⋮ Computing a context-free grammar-generating series ⋮ Number of prefixes in trace monoids: clique polynomials and dependency graphs ⋮ Basic analytic combinatorics of directed lattice paths ⋮ A context-free language decision problem ⋮ Context-free languages of sub-exponential growth
Cites Work
- A note on the density of inherently ambiguous context-free languages
- Differentiably finite power series
- String overlaps, pattern matching, and nontransitive games
- On the number of words in the language \(\{w \epsilon \Sigma^* | w=w^ r\}^ 2\)
- The average height of binary trees and other simple trees
- Integral transforms and their applications
- The sixty system of Sumer
- Calcul pratique des coefficients de Taylor d'une fonction algébrique
- Uniform Random Generation of Strings in a Context-Free Language
- The characterization of nonexpansive grammars by rational power series
- The structure generating function of some families of languages
- On the Altitude of Nodes in Random Trees
- Some inherently ambiguous context-free languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Analytic models and ambiguity of context-free languages
