Pith. sign in

REVIEW 3 major objections 3 minor 86 references

For probabilistic words, membership in unambiguous context-free languages is computable in polynomial time, while some mildly ambiguous cases are already #P-hard.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 10:48 UTC pith:V7KQKJ3C

load-bearing objection Genuinely new problem and substantial complexity landscape, but the Section 5 example that circuits beat poly-slicewise-unambiguity is broken as written. the 3 major comments →

arxiv 2510.08127 v2 pith:V7KQKJ3C submitted 2025-10-09 cs.FL

On the Complexity of Language Membership for Probabilistic Words

Antoine Amarilli , Mika\"el Monet , Paul Rapha\"el , Sylvain Salvati This is my paper
classification cs.FL MSC 68Q4568Q1768Q15
keywords probabilistic wordscontext-free languagesunambiguous grammars#P-hardnesspoly-slicewise-unambiguoustractable circuitsprimitive wordspalindrome concatenation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces probabilistic membership: given a word in which each position carries a probability distribution over letters, compute the probability that a randomly drawn word belongs to a fixed language. The paper shows that unambiguity is a broad source of tractability—unambiguous context-free languages are solvable in cubic polynomial time—and introduces a hierarchy of poly-slicewise-unambiguous languages and tractable circuits that extends tractability to some inherently ambiguous languages. It proves that hardness starts very early: the problem is #P-hard already for unions of two linear unambiguous context-free languages, though it remains tractable for bounded CFLs and unambiguous polynomial-time counter automata. The circuit framework, enriched with complementation, yields polynomial-time algorithms for primitive words and concatenations of two palindromes. Finally, assuming FP≠#P, deciding from a grammar whether its probabilistic membership is tractable is undecidable.

Core claim

The paper's central claim is that probabilistic membership mirrors a grammar's ambiguity structure: with at most one parse tree per word, summing probabilities of derivation trees is exact and runs in polynomial time; once ambiguity is allowed, the problem can become #P-hard, already for a union of two linear unambiguous grammars. The paper develops a circuit calculus—×,⊎-circuits with decomposable products, deterministic disjoint unions, and optional complementation—that represents the length-n slice of a language as a factorized set of assignments, so the desired probability is computed by a single bottom-up pass of multiplications, additions, and complements. This calculus subsumes poly-s

What carries the argument

The central device is a circuit representation of a language's length slices. A ×,⊎-circuit is a directed acyclic circuit whose ×-gates build Cartesian products over disjoint position domains (decomposable) and whose ⊎-gates build disjoint unions of equal-domain assignment sets (deterministic and smooth); probabilities evaluate in linear time by multiplying at ×-gates and summing at ⊎-gates. Adding ∁-gates, which complement the assignment set of a subcircuit, preserves this linear evaluation and enables inclusion–exclusion constructions. For the two-palindrome language, the key mechanism is a partition of words by the order and offset of their primitive-root decomposition into two palindrome

Load-bearing premise

The tractability of the two-palindrome language rests on the imported combinatorial claim that every word in that language has a unique primitive-root decomposition into two palindromes; if that claim ever fails, the partition used by the algorithm double-counts and the polynomial-time guarantee collapses.

What would settle it

A brute-force check on small alphabets (e.g., all words over {a,b} up to length 12) comparing the O(n^3|Σ|) circuit-based count with the true count of the two-palindrome language would falsify the algorithm; a direct refutation would be finding one word in that language whose primitive root splits into palindromes in two distinct ways.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Probabilistic membership is in PTIME, in fact in O(n^3|Γ|) in combined complexity, for every unambiguous context-free grammar, covering deterministic CFLs and all regular languages.
  • The problem is #P-hard already for a union of two linear unambiguous CFLs, and also for some languages recognized by nondeterministic one-counter and Parikh automata.
  • Every poly-slicewise-unambiguous language, including all bounded/polyslender CFLs and languages of unambiguous polynomial-time counter automata, has polynomial-time probabilistic membership.
  • Languages admitting tractable ×,⊎-circuits or ×,⊎,∁-circuits have polynomial-time probabilistic membership; this class is strictly larger than poly-slicewise-unambiguous languages.
  • Assuming FP≠#P, the meta-problem of deciding from a linear CFG whether its probabilistic membership problem is tractable is undecidable.
  • Tractable probabilistic membership for a language implies efficient sampling, enumeration, and ranking in radix order via self-reducibility.
  • The tractability results extend to complements of the studied languages, because complementation can be handled by subtracting the answer from 1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The circuit-based criterion suggests a broader measurement: what matters is whether each length-n slice can be represented by a small factorized, disjoint decomposition; this points to knowledge compilation as the natural lens for characterizing tractable languages beyond grammars.
  • If the uniqueness lemma on primitive roots of two-palindrome words generalizes to longer palindromic factorizations, the same complement-based construction could make PAL3 or palindromic stars tractable; the paper explicitly leaves this open.
  • The conditional undecidability of the meta-problem hints that any eventual full dichotomy for probabilistic membership would need input beyond the bare grammar—for example, a semantics-preserving normal form or an oracle for ambiguity—rather than a syntactic check.
  • Because the hardness proofs work even when wildcards are restricted to a two-letter subalphabet, the #P-hardness is intrinsic to counting completions, not an artifact of rich probability values.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper introduces and studies the probabilistic membership problem for context-free languages: given a probabilistic word (a sequence of per-position distributions over an alphabet) and a fixed language L, compute the total probability that a random word drawn from the product distribution belongs to L. The authors establish a complexity landscape: the problem is in polynomial time for unambiguous CFLs (Proposition 3.1); it is #P-hard for some unions of two linear uCFLs (Proposition 3.6); it is tractable for the newly introduced class of poly-slicewise-unambiguous languages, covering bounded CFLs and unambiguous polynomial-time counter automata; it remains #P-hard for some nondeterministic one-counter/Parikh automata. The paper then introduces tractable ×,⊎-circuits and ×,⊎,∁-circuits from knowledge compilation, claiming these strictly generalize poly-slicewise-unambiguity, and uses them to prove tractability for primitive words (Proposition 6.4) and for the concatenation of two palindromes PAL2 (Theorem 6.9). Finally, it claims a conditional undecidability result for the meta-problem of deciding, from a CFG, whether the corresponding #pM problem is tractable or #P-hard (Proposition 7.1). The body gives proof sketches, with detailed proofs in the appendices.

Significance. If the main claims were established, this would be a valuable contribution to the complexity of weighted counting for context-free languages, connecting formal-language theory with knowledge compilation. The positive results for uCFLs (via a weighted CYK-style dynamic program), the #P-hardness reductions via PP2DNF and Turing-machine runs, the poly-slicewise-unambiguous framework, and the circuit constructions are well-motivated and largely coherent. The paper also gives explicit polynomial-time algorithms for primitive words and PAL2 that go beyond what follows from unambiguity, and it identifies a natural class (poly-slicewise-unambiguity) that unifies several otherwise disparate tractable cases. The detailed appendix is a strength. However, as detailed below, several load-bearing points are currently not correct as written: Claim 5.5's circuit mismatch for L3, a non-constructive step in Proposition 7.1's undecidability reduction, and a disjointness error in the PAL2 circuit construction. These issues affect the paper's headline claims and need to be repaired.

major comments (3)
  1. [Section 5, Claim 5.5] The circuit construction does not capture the language L3 as formally defined. The definition L3 = {(a+b)^k a (a+b)^n a (a+b)^{n-k-2}} places n letters between the two a's, so the two a-positions differ by n+1. The OBDD in Claim 5.5 tests pairs (i, i+n), whose positions differ by n. For input length 4, 'abba' is in L3 (a's at positions 1 and 4) but the constructed circuit rejects it, while 'baaa' (a's at positions 2 and 4) is accepted but not in L3. Thus the circuit captures a different language (two a's at index distance n), not L3 as defined. Since L3 is the paper's only evidence that tractable circuits strictly generalize poly-slicewise-unambiguity, Claim 5.5 as written is unsupported.
  2. [Appendix E.4, Claim E.6 / Theorem 6.9] The proof of tractability for PAL2 relies on a disjoint union that is false. Claim E.6 asserts that M_{n,d,j} is the disjoint union of the L_{n,pd,j mod (n/pd)} sets. This conflates the offset of a decomposition of v (where u = v^d) with the unique offset of the primitive root of u guaranteed by Lemma 6.10. A word in PAL2 may have several decompositions into two palindromes even when its primitive root has a unique one. For example, 'abab' is in M_{4,1,1} (decomposition 'a' + 'bab') and also in M_{4,1,3} (decomposition 'aba' + 'b'), so the claimed disjointness fails. Consequently Equation (3) and the ensuing induction do not establish that PAL2 admits tractable ×,⊎,∁-circuits, and Theorem 6.9 is not supported by the proof given.
  3. [Appendix F, Proposition 7.1] The proof of conditional undecidability is not a valid reduction as written. In the hardness direction for a non-universal Γ, the reduction is supposed to map an input p for #pM(L0) to the probabilistic word wp, where w is 'an arbitrary word w ∉ L(Γ)'. But such a w is not computable from Γ in general: the reduction is not effective. A many-one reduction must be a computable function of Γ; merely knowing that a witness exists is insufficient. The paper's appeal that 'we do not care about the decidability of picking this constant word' is not acceptable for a complexity-theoretic reduction. The claim may be salvageable, e.g., using Greibach's theorem or a different construction, but the proof as stated does not establish Proposition 7.1.
minor comments (3)
  1. [Section 5] The informal phrase 'words of length 2n which contain two occurrences of a at distance exactly n' is ambiguous and is the source of the mismatch in Claim 5.5. If the intended language is the one in the formal definition, the distance (position difference) is n+1; if the intended language is the one captured by the circuit, the formal definition should be changed to place n-1 letters between the two a's.
  2. [Appendix B.2] In the proof of Proposition 3.5, the sentence 'The proof is the same as Proposition 3.5' should refer to Proposition 3.4.
  3. [Section 6] Lemma 6.10 is imported from [53] and is load-bearing for the PAL2 result. Given the extensive use of the unique-decomposition property in the circuit construction, the paper should either state and prove Lemma 6.10 or give a precise citation with the exact statement, as the current proof of Theorem 6.9 depends on it structurally.

Circularity Check

0 steps flagged

No circular dependency; Claim 5.5's off-by-one is a correctness bug, not a circular reduction.

full rationale

I walked the derivation chain and found no step where a claimed prediction or first-principles result reduces to its own inputs by construction. The uCFL tractability result (Prop. 3.1) is a direct CYK-style weighted counting over parse trees, with unambiguity preventing double counting; the poly-slicewise-unambiguous result (Prop. 4.2) is an immediate reduction to Prop. 3.1 but is not circular because the uCFG for the slice is computed separately by the definition's algorithm. The #P-hardness proofs reduce from #PP2DNF or from run-counting of Turing machines via explicit encodings, with the external facts ([80], [82], [8]) being cited as independent results. The circuit framework is defined and proved in the paper, with the tractable counting lemma imported from Darwiche [25]; the PAL2 result rests on the external combinatorial Lemma 6.10 from Kemp [53], not on a theorem of the present authors. Self-citations such as [4], [5], and [6] are contextual, motivational, or delegate to standard independent proofs; none is the sole load-bearing support for a central claim. The one substantive flaw I found is not circularity: Claim 5.5's OBDD construction tests pairs at index distance k, while the L3 definition with (a+b)^n places n letters between the two a's, so as written the circuit captures a different slice-language. This is an internal correctness/off-by-one issue in the paper's strict-generalization example, not a reduction of a prediction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 8 axioms · 2 invented entities

The paper is purely mathematical: there are no free parameters fitted to data. The central claims rest on the external theorems listed above and on explicitly stated definitions. The new complexity classes and circuit formalisms are introduced as definitions; their scientific value is the nontrivial constructions for concrete CFLs, not any independent empirical prediction.

axioms (8)
  • standard math #PP2DNF is #P-hard (Theorem 3.3, citing [82,80]).
    Used as the source of hardness in Propositions 3.4 and 4.8; if this counting problem were tractable, the hardness results would collapse.
  • domain assumption Transformation to 2NF preserves unambiguity of CFGs, as cited to [60] and [5, Appendix A.2].
    Used in the proofs of Proposition 3.1 and Proposition 5.3 to justify the CYK-style probability dynamic program.
  • domain assumption Baker–Book encoding of Turing-machine runs can be enforced by linear context-free grammars, and universality of linear CFGs is undecidable [8].
    Used in Proposition 3.6 for hardness of unions of two linear uCFLs, and in Proposition 7.1 for the conditional undecidability of the meta-problem.
  • domain assumption Bounded CFLs are exactly the polyslender CFLs [35,47].
    Used in Section 4 to conclude that bounded/polyslender CFLs are poly-slicewise-unambiguous via explicit enumeration of words.
  • domain assumption For every word in PAL2, its primitive root decomposes uniquely into two palindromes (Lemma 6.10, from [53]).
    Load-bearing for Theorem 6.9; the circuit construction partitions PAL2 by order and offset using this uniqueness.
  • domain assumption The language L3 = {(a+b)^k a (a+b)^n a (a+b)^{n-k-2}} has length-n slices requiring exponential-size uCFGs [65, Theorem 1].
    Used in Section 5 to show the tractable-circuit formalism strictly extends poly-slicewise-unambiguity.
  • domain assumption The conditional assumption FP ≠ #P for Proposition 7.1.
    The undecidability of the meta-problem is proved only under this complexity assumption, as stated in the theorem.
  • standard math Primitive root uniqueness (Shallit [77, Theorem 2.3.4]).
    Used in the primitive-words construction to partition words by order and to build circuits for the L_k languages.
invented entities (2)
  • poly-slicewise-unambiguous languages no independent evidence
    purpose: A sufficient condition for polynomial-time probabilistic membership: a language whose length-n slice can be recognized by a uCFG computable in PTIME in n.
    New definition introduced in Section 4. It has no external empirical handle; its value is demonstrated by unifying uCFLs and bounded CFLs and by the subsequent circuit constructions.
  • tractable ×,⊎-circuits and ×,⊎,∁-circuits no independent evidence
    purpose: Factorized circuit representations of partial assignments; probabilities are computable in linear time by bottom-up evaluation, and are used to prove tractability for L3, primitive words, and PAL2.
    Adapted from sd-DNNF and d-D circuits in knowledge compilation; the counting property is proven internally, but the entities themselves are definitions rather than empirically testable postulates.

pith-pipeline@v1.3.0-alltime-deepseek · 33132 in / 17949 out tokens · 143910 ms · 2026-08-04T10:48:13.419238+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of On the Complexity of Language Membership for Probabilistic Words." pith.science (2026). https://pith.science/paper/V7KQKJ3C

@misc{pith2026251008127,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of Language Membership for Probabilistic Words},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V7KQKJ3C}},
  note         = {Machine review of arXiv:2510.08127}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We study the membership problem to context-free languages (CFLs) on probabilistic words, that specify for each position a probability distribution on the letters. Our task is to compute, given a probabilistic word, what is the probability that a word drawn according to the distribution belongs to the language $L$. This problem generalizes the problem of counting how many words of length $n$ belong to $L$, or of counting how many completions of a partial word belong to $L$. We show that this problem is in polynomial time for unambiguous context-free languages (uCFLs), but can be #P-hard already for unions of two linear uCFLs. More generally, we show that the problem is in polynomial time for so-called poly-slicewise-unambiguous languages, where given a length $n$ we can tractably compute an uCFL for the words of length $n$ in the language. This class includes some inherently ambiguous languages, and implies the tractability of bounded CFLs and of languages recognized by unambiguous polynomial-time counter automata. We then introduce classes of circuits from knowledge compilation which we use for tractable counting, and show that this covers the tractability of poly-slicewise-unambiguous languages and of some CFLs that are not poly-slicewise-unambiguous. Extending these circuits with negation further allows us to show tractability for the language of primitive words, and for the language of concatenations of two palindromes. We also show that, when the target language is given as input, our problem is intractable already when the language asks whether there is a factor that matches one partial word; however, it becomes tractable when the language is given as a $k$-ambiguous automaton for any fixed $k>0$. We finally show the conditional undecidability of the meta-problem that asks, given a CFG, whether the probabilistic membership problem for that CFG is tractable or #P-hard.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

86 extracted references · 1 canonical work pages

  1. [1]

    If the current clique algorithms are optimal, so is V aliant's parser

    Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is V aliant's parser. SIAM Journal on Computing , 47(6), 2018

    2018

  2. [2]

    A very hard log-space counting class

    Carme \`A lvarez and Birgit Jenner. A very hard log-space counting class. Theoretical Computer Science , 107(1), 1993

    1993

  3. [3]

    Context-free grammars where every word has exactly two derivation trees

    Antoine Amarilli. Context-free grammars where every word has exactly two derivation trees. Theoretical Computer Science Stack Exchange, 2025. https://cstheory.stackexchange.com/q/55726

    2025

  4. [4]

    Tractable circuits in database theory

    Antoine Amarilli and Florent Capelli. Tractable circuits in database theory. ACM SIGMOD Record , 53(2), 2024

    2024

  5. [5]

    https://arxiv.org/abs/2201.00549 Efficient enumeration algorithms for annotated grammars

    Antoine Amarilli, Louis Jachiet, Martín Muñoz, and Cristian Riveros. https://arxiv.org/abs/2201.00549 Efficient enumeration algorithms for annotated grammars . In PODS https://2022.sigmod.org/ , 2022. https://doi.org/10.1145/3517804.3526232 doi:10.1145/3517804.3526232

    Pith/arXiv arXiv 2022

  6. [6]

    https://arxiv.org/abs/2401.16210 The non-cancelling intersections conjecture

    Antoine Amarilli, Mikaël Monet, and Dan Suciu. https://arxiv.org/abs/2401.16210 The non-cancelling intersections conjecture . Preprint: https://arxiv.org/abs/2401.16210, 2024

    Pith/arXiv arXiv 2024

  7. [7]

    \# NFA admits an FPRAS : E fficient enumeration, counting, and uniform generation for logspace classes

    Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. \# NFA admits an FPRAS : E fficient enumeration, counting, and uniform generation for logspace classes. Journal of the ACM , 68(6), 2021

    2021

  8. [8]

    Baker and Ronald V

    Brenda S. Baker and Ronald V. Book. Reversal-bounded multipushdown machines. Journal of Computer and System Sciences , 8(3), 1974

    1974

  9. [9]

    Berstel and L

    J. Berstel and L. Boasson. Context-free languages. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, vol B , chapter 2. MIT Press, 1990. https://www-igm.univ-mlv.fr/ berstel/Articles/1990HandbookCfl.pdf

    1990

  10. [10]

    Partial words and a theorem of F ine and W ilf

    Jean Berstel and Luc Boasson. Partial words and a theorem of F ine and W ilf. Theoretical Computer Science , 218(1), 1999

    1999

  11. [11]

    Ranking and formal power series

    Alberto Bertoni, Danilo Bruschi, and Massimiliano Goldwurm. Ranking and formal power series. Theoretical computer science , 79(1), 1991

    1991

  12. [12]

    The complexity of computing the number of strings of given length in context-free languages

    Alberto Bertoni, Massimiliano Goldwurm, and Nicoletta Sabadini. The complexity of computing the number of strings of given length in context-free languages. Theoretical Computer Science , 86(2), 1991

    1991

  13. [13]

    Random generation for finitely ambiguous context-free languages

    Alberto Bertoni, Massimiliano Goldwurm, and Massimo Santini. Random generation for finitely ambiguous context-free languages. RAIRO-Theoretical Informatics and Applications , 35(6), 2001

    2001

  14. [14]

    Counting distinct squares in partial words

    Francine Blanchet-Sadri, Robert Merca s , and Geoffrey Scott. Counting distinct squares in partial words. Acta Cybernetica , 19(2), 2009

    2009

  15. [15]

    Words with many palindrome pair factors

    Adam Borchert and Narad Rampersad. Words with many palindrome pair factors. The Electronic Journal of Combinatorics , 2015

    2015

  16. [16]

    On the palindromic complexity of infinite words

    Srecko Brlek, Sylvie Hamel, Maurice Nivat, and Christophe Reutenauer. On the palindromic complexity of infinite words. International Journal of Foundations of Computer Science , 15(02), 2004

    2004

  17. [17]

    Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers , 100(8), 1986

    1986

  18. [18]

    P \'e rez, and Ritam Raha

    Micha \"e l Cadilhac, Arka Ghosh, Guillermo A. P \'e rez, and Ritam Raha. Parikh one-counter automata. Information and Computation , 2025

    2025

  19. [19]

    On the complexity of the universality and inclusion problems for unambiguous context-free grammars, 2020

    Lorenzo Clemente. On the complexity of the universality and inclusion problems for unambiguous context-free grammars, 2020. Preprint: https://arxiv.org/abs/2008.04667

    Pith/arXiv arXiv 2020

  20. [20]

    Separability of reachability sets of vector addition systems

    Lorenzo Clemente, Wojciech Czerwi \'n ski, S awomir Lasota, and Charles Paperman. Separability of reachability sets of vector addition systems. In STACS , 2017

    2017

  21. [21]

    Unambiguity in automata theory

    Thomas Colcombet. Unambiguity in automata theory. In International Workshop on Descriptional Complexity of Formal Systems , 2015

    2015

  22. [22]

    Naive infinite enumeration of context-free languages in incremental polynomial time

    Christophe Costa Florencio, Jonny Daenen, Jan Ramon, Jan Van den Bussche, and Dries Van Dyck. Naive infinite enumeration of context-free languages in incremental polynomial time. Journal of Universal Computer Science , 21(7), 2015

    2015

  23. [23]

    J.P. Crestin. Un langage non ambigu dont le carré est d'ambiguïté non-bornée. In ICALP , 1972

    1972

  24. [24]

    An approach to regular separability in vector addition systems

    Wojciech Czerwi \'n ski and Georg Zetzsche. An approach to regular separability in vector addition systems. In LICS , 2020

    2020

  25. [25]

    On the tractable counting of theory models and its application to truth maintenance and belief revision

    Adnan Darwiche. On the tractable counting of theory models and its application to truth maintenance and belief revision. Journal of Applied Non-Classical Logics , 11(1-2), 2001

    2001

  26. [26]

    A knowledge compilation map

    Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research , 17, 2002

    2002

  27. [27]

    On some combinatorial problems in free monoids

    Aldo de Luca. On some combinatorial problems in free monoids. Discrete Mathematics , 38(2-3), 1982

    1982

  28. [28]

    Some combinatorial properties of sturmian words

    Aldo de Luca and Filippo Mignosi. Some combinatorial properties of sturmian words. Theoretical Computer Science , 136(2), 1994

    1994

  29. [29]

    Unusual algorithms for lexicographical enumeration

    P \'a l D \"o m \"o si. Unusual algorithms for lexicographical enumeration. Acta Cybernetica , 14(3), 2000

    2000

  30. [30]

    An efficient context-free parsing algorithm

    Jay Earley. An efficient context-free parsing algorithm. Communications of the ACM , 13(2), 1970

    1970

  31. [31]

    Some remarks on palindromic periodicities

    Gabriele Fici, Jeffrey Shallit, and Jamie Simpson. Some remarks on palindromic periodicities. Preprint: https://arxiv.org/pdf/2407.10567, 2024

    Pith/arXiv arXiv 2024

  32. [32]

    Fischer, Albert R

    Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. Counter machines and counter languages. Mathematical systems theory , 2(3), 1968

    1968

  33. [33]

    Frid, Svetlana Puzynina, and Luca Q

    Anna E. Frid, Svetlana Puzynina, and Luca Q. Zamboni. On palindromic factorization of words. Advances in Applied Mathematics , 50(5), 2013

    2013

  34. [34]

    Deterministic context free languages

    Seymour Ginsburg and Sheila Greibach. Deterministic context free languages. In SWCT , 1965

    1965

  35. [35]

    Bounded algol-like languages

    Seymour Ginsburg and Edwin H Spanier. Bounded algol-like languages. Transactions of the American Mathematical Society , 113(2), 1964

    1964

  36. [36]

    Sweedyk, and Steve Mahaney

    Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, and Steve Mahaney. A quasi-polynomial-time algorithm for sampling words from a context-free language. Information and Computation , 134(1), 1997

    1997

  37. [37]

    A note on undecidable properties of formal languages https://doi.org/10.1007/BF01691341

    Sheila Greibach. A note on undecidable properties of formal languages https://doi.org/10.1007/BF01691341. Mathematical systems theory , 2, 1968. https://doi.org/10.1007/BF01691341 doi:10.1007/BF01691341

    work page doi:10.1007/bf01691341 1968

  38. [38]

    Greibach

    Sheila A. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science , 7(3), 1978

    1978

  39. [39]

    Chuan Guo, Jeffrey Shallit, and Arseny M. Shur. On the combinatorics of palindromes and antipalindromes. Preprint: https://arxiv.org/abs/1503.09112, 2015

    Pith/arXiv arXiv 2015

  40. [40]

    Hartmanis

    J. Hartmanis. Context-free languages and turing machine computations. In Proceedings of Symposia in Applied Mathematics , 1967

    1967

  41. [41]

    Hibbard and Joseph Ullian

    Thomas N. Hibbard and Joseph Ullian. The independence of inherent ambiguity from complementedness among context-free languages. Journal of the ACM , 13(4), 1966

    1966

  42. [42]

    Uniform random generation of strings in a context-free language

    Timothy Hickey and Jacques Cohen. Uniform random generation of strings in a context-free language. SIAM Journal on Computing , 12(4), 1983

    1983

  43. [43]

    Pumping lemmas for linear and nonlinear context-free languages

    G \'e za Horv \'a th and Benedek Nagy. Pumping lemmas for linear and nonlinear context-free languages. Preprint: https://arxiv.org/abs/1012.0023, 2010

    Pith/arXiv arXiv 2010

  44. [44]

    Strong interchangeability and nonlinearity of primitive words

    S \'a ndor Horv \'a th. Strong interchangeability and nonlinearity of primitive words. Algebraic Methods in Language Processing , 1995

    1995

  45. [45]

    Dung T. Huynh. The complexity of ranking. In Structure in Complexity Theory , 1988

    1988

  46. [46]

    Dung T. Huynh. The complexity of ranking simple languages. Mathematical Systems Theory , 23(1), 1990

    1990

  47. [47]

    A characterization of poly-slender context-free languages

    Lucian Ilie, Grzegorz Rozenberg, and Arto Salomaa. A characterization of poly-slender context-free languages. RAIRO-Theoretical Informatics and Applications , 34(1), 2000

    2000

  48. [48]

    Context-free languages and primitive words

    Masami Ito and Pal Domosi. Context-free languages and primitive words . World Scientific, 2014

    2014

  49. [49]

    Knowledge compilation meets database theory: Compiling queries to decision diagrams

    Abhay Jha and Dan Suciu. Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory of Computing Systems , 2013

    2013

  50. [50]

    Multidimensional trees and a C homsky- S ch \" u tzenberger- W eir representation theorem for simple context-free tree grammars

    Makoto Kanazawa. Multidimensional trees and a C homsky- S ch \" u tzenberger- W eir representation theorem for simple context-free tree grammars. J. Log. Comput. , 26(5), 2016

    2016

  51. [51]

    Kobele, Jens Michaelis, Sylvain Salvati, and Ryo Yoshinaka

    Makoto Kanazawa, Gregory M. Kobele, Jens Michaelis, Sylvain Salvati, and Ryo Yoshinaka. The failure of the strong pumping lemma for multiple context-free languages. Theory Comput. Syst. , 55(1), 2014

    2014

  52. [52]

    Karp and Raymond E

    Richard M. Karp and Raymond E. Miller. Parallel program schemata. Journal of Computer and system Sciences , 3(2), 1969

    1969

  53. [53]

    R. Kemp. On the number of words in the language \ w ^* w = w^R\ ^2 . Discrete Mathematics , 40(2), 1982

    1982

  54. [54]

    A formal language perspective on factorized representations

    Benny Kimelfeld, Wim Martens, and Matthias Niewerth. A formal language perspective on factorized representations. In ICDT , 2025

    2025

  55. [55]

    Monadic second-order logics with cardinalities

    Felix Klaedtke and Harald Rue . Monadic second-order logics with cardinalities. In International Colloquium on Automata, Languages, and Programming , 2003

    2003

  56. [56]

    Knuth, James H

    Donald E. Knuth, James H. Morris, Jr, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing , 6(2), 1977

    1977

  57. [57]

    New analytic techniques for proving the inherent ambiguity of context-free languages

    Florent Koechlin. New analytic techniques for proving the inherent ambiguity of context-free languages. In FSTTCS , volume 250, 2022

    2022

  58. [58]

    An operational and denotational approach to non-context-freeness

    Hans-Peter Kolb, Jens Michaelis, Uwe Mönnich, and Frank Morawietz. An operational and denotational approach to non-context-freeness. Theoretical Computer Science , 293(2), 2003

    2003

  59. [59]

    Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur. Pal ^k is linear recognizable online. In SOFSEM , 2015

    2015

  60. [60]

    https://www.informaticadidactica.de/uploads/Artikel/LangeLeiss2009/LangeLeiss2009.pdf To CNF or not to CNF ? An efficient yet presentable version of the CYK algorithm

    Martin Lange and Hans Lei . https://www.informaticadidactica.de/uploads/Artikel/LangeLeiss2009/LangeLeiss2009.pdf To CNF or not to CNF ? An efficient yet presentable version of the CYK algorithm . Informatica Didactica , 8(2009), 2009

    2009

  61. [61]

    Harry G. Mairson. Generating words in a context-free language uniformly at random. Information Processing Letters , 49(2), 1994

    1994

  62. [62]

    On lexicographic enumeration of regular and context-free languages

    Erkki M \"a kinen. On lexicographic enumeration of regular and context-free languages. Acta Cybernetica , 13(1), 1997

    1997

  63. [63]

    Hard counting problems for partial words

    Florin Manea and C a t a lin Tiseanu. Hard counting problems for partial words. In International Conference on Language and Automata Theory and Applications , 2010

    2010

  64. [64]

    Meel and Alexis de Colnet

    Kuldeep S. Meel and Alexis de Colnet. \# CFG and \# DNNF admit FPRAS . Preprint: https://arxiv.org/abs/2406.18224, 2024

    Pith/arXiv arXiv 2024

  65. [65]

    A lower bound on unambiguous context free grammars via communication complexity

    Stefan Mengel and Harry Vinall-Smeeth. A lower bound on unambiguous context free grammars via communication complexity. PACMMOD , 3(2), 2025

    2025

  66. [66]

    Solving a special case of the intensional vs extensional conjecture in probabilistic databases

    Mika \"e l Monet. Solving a special case of the intensional vs extensional conjecture in probabilistic databases. In PODS , 2020

    2020

  67. [67]

    Lecture notes on automata, languages, and grammars, 2012

    Cristopher Moore. Lecture notes on automata, languages, and grammars, 2012. https://sites.santafe.edu/ moore/500/automata-notes.pdf

    2012

  68. [68]

    Unambiguous boolean grammars

    Alexander Okhotin. Unambiguous boolean grammars. Information and Computation , 206(9-10), 2008

    2008

  69. [69]

    Conjunctive and boolean grammars: T he true general case of the context-free grammars

    Alexander Okhotin. Conjunctive and boolean grammars: T he true general case of the context-free grammars. Computer Science Review , 9, 2013

    2013

  70. [70]

    The ambiguity of primitive words

    Holger Petersen. The ambiguity of primitive words. In STACS , 1994

    1994

  71. [71]

    New compilation languages based on structured decomposability

    Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based on structured decomposability. In AAAI , volume 8, 2008

    2008

  72. [72]

    e l Fijalkow. The universality problem for automata with bounded ambiguity. “Games Automata Play

    Ritam Raha and Nathana\" e l Fijalkow. The universality problem for automata with bounded ambiguity. “Games Automata Play” blog, 2018. https://games-automata-play.github.io/blog/universality_finitely_ambiguous/. Accessed: September 12, 2025

    2018

  73. [73]

    Mikhail Rubinchik and Arseny M. Shur. Palindromic k-factorization in pure linear time. In MFCS , 2020

    2020

  74. [74]

    Deciding equivalence of finite tree automata

    Helmut Seidl. Deciding equivalence of finite tree automata. SIAM Journal on Computing , 19(3), 1990

    1990

  75. [75]

    On multiple context-free grammars

    Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. On multiple context-free grammars. Theoretical Computer Science , 88(2), 1991

    1991

  76. [76]

    Generation of all the balanced parenthesis strings in lexicographical order

    Ichiro Semba. Generation of all the balanced parenthesis strings in lexicographical order. Information Processing Letters , 12(4), 1981

    1981

  77. [77]

    A second course in formal languages and automata theory

    Jeffrey Shallit. A second course in formal languages and automata theory . Cambridge University Press, 2008

    2008

  78. [78]

    Some inherently ambiguous context-free languages

    Eliahu Shamir. Some inherently ambiguous context-free languages. Information and Control , 18(4), 1971

    1971

  79. [79]

    Hunt III

    Richard Edwin Stearns and Harry B. Hunt III. On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM Journal on Computing , 14(3), 1985

    1985

  80. [80]

    Suciu, D

    D. Suciu, D. Olteanu, and C. Koch. Probabilistic Databases . Synthesis digital library of engineering and computer science. Morgan & Claypool Publishers, 2011

    2011

Showing first 80 references.