Analytic models and ambiguity of context-free languages (Q1088414): Difference between revisions

We establish that several classical context-free languages are inherently ambiguous by proving that their counting generating functions, when considered as analytic functions, exhibit some characteristic form of transcendental behaviour. To that purpose, we survey some general results on elementary analytic properties and enumerative uses of algebraic functions in relation to formal languages. In particular, the paper contains a general density theorem for unambiguous context-free languages.

0 references

zbMATH Keywords

counting generating functions

0 references

analytic functions

0 references

transcendental behaviour

0 references

algebraic functions

0 references

general density theorem for unambiguous context-free languages

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q3873564

0 references

The characterization of nonexpansive grammars by rational power series

0 references

Q4723318

0 references

Q5621389

0 references

Q5526125

0 references

Calcul pratique des coefficients de Taylor d'une fonction algébrique

0 references

Q4769056

0 references

Q4403740

0 references

Integral transforms and their applications

0 references

Q5537802

0 references

Q5798359

0 references

The average height of binary trees and other simple trees

0 references

Q3704890

0 references

Q3263792

0 references

String overlaps, pattern matching, and nontransitive games

0 references

Q5779465

0 references

Q4198075

0 references

Q4156973

0 references

Uniform Random Generation of Strings in a Context-Free Language

0 references

Q3742754

0 references

On the number of words in the language \(\{w \epsilon \Sigma^* | w=w^ r\}^ 2\)

0 references

A note on the density of inherently ambiguous context-free languages

0 references

Q4138831

0 references

Q4161406

0 references

Q3704880

0 references

The structure generating function of some families of languages

0 references

On the Altitude of Nodes in Random Trees

0 references

Q4405392

0 references

Q4155837

0 references

Q3241279

0 references

The sixty system of Sumer

0 references

Some inherently ambiguous context-free languages

0 references

Differentiably finite power series

0 references

Q3844537

0 references

Identifiers

zbMATH Open document ID

0612.68069

0 references

DOI

10.1016/0304-3975(87)90011-9

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1088414

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1997965066
@@ Property / OpenAlex ID: W1997965066 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3873564
@@ Property / cites work: Q3873564 / rank @@
+Normal rank
@@ Property / cites work @@
+The characterization of nonexpansive grammars by rational power series
+Normal rank
@@ Property / cites work @@
+Q4723318
@@ Property / cites work: Q4723318 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5621389
@@ Property / cites work: Q5621389 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5526125
@@ Property / cites work: Q5526125 / rank @@
+Normal rank
@@ Property / cites work @@
+Calcul pratique des coefficients de Taylor d'une fonction algébrique
+Normal rank
@@ Property / cites work @@
+Q4769056
@@ Property / cites work: Q4769056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4403740
@@ Property / cites work: Q4403740 / rank @@
+Normal rank
@@ Property / cites work @@
+Integral transforms and their applications
@@ Property / cites work: Integral transforms and their applications / rank @@
+Normal rank
@@ Property / cites work @@
+Q5537802
@@ Property / cites work: Q5537802 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5798359
@@ Property / cites work: Q5798359 / rank @@
+Normal rank
@@ Property / cites work @@
+The average height of binary trees and other simple trees
+Normal rank
@@ Property / cites work @@
+Q3704890
@@ Property / cites work: Q3704890 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3263792
@@ Property / cites work: Q3263792 / rank @@
+Normal rank
@@ Property / cites work @@
+String overlaps, pattern matching, and nontransitive games
+Normal rank
@@ Property / cites work @@
+Q5779465
@@ Property / cites work: Q5779465 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198075
@@ Property / cites work: Q4198075 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4156973
@@ Property / cites work: Q4156973 / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform Random Generation of Strings in a Context-Free Language
+Normal rank
@@ Property / cites work @@
+Q3742754
@@ Property / cites work: Q3742754 / rank @@
+Normal rank
@@ Property / cites work @@
+On the number of words in the language \(\{w \epsilon \Sigma^* | w=w^ r\}^ 2\)
+Normal rank
@@ Property / cites work @@
+A note on the density of inherently ambiguous context-free languages
+Normal rank
@@ Property / cites work @@
+Q4138831
@@ Property / cites work: Q4138831 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4161406
@@ Property / cites work: Q4161406 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3704880
@@ Property / cites work: Q3704880 / rank @@
+Normal rank
@@ Property / cites work @@
+The structure generating function of some families of languages
+Normal rank
@@ Property / cites work @@
+On the Altitude of Nodes in Random Trees
@@ Property / cites work: On the Altitude of Nodes in Random Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Q4405392
@@ Property / cites work: Q4405392 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4155837
@@ Property / cites work: Q4155837 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3241279
@@ Property / cites work: Q3241279 / rank @@
+Normal rank
@@ Property / cites work @@
+The sixty system of Sumer
@@ Property / cites work: The sixty system of Sumer / rank @@
+Normal rank
@@ Property / cites work @@
+Some inherently ambiguous context-free languages
@@ Property / cites work: Some inherently ambiguous context-free languages / rank @@
+Normal rank
@@ Property / cites work @@
+Differentiably finite power series
@@ Property / cites work: Differentiably finite power series / rank @@
+Normal rank
@@ Property / cites work @@
+Q3844537
@@ Property / cites work: Q3844537 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1088414