Pith. sign in

REVIEW 3 major objections 5 minor 42 references

Syntax Repair as Language Intersection

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Bounded syntax repair is exactly the intersection of a grammar with an acyclic Levenshtein automaton, and nonemptiness of that intersection is decidable in polylogarithmic parallel time.

desk verdict A genuinely useful practical framing of syntax repair as finite CFL intersection is undermined by a false parallel-complexity theorem and an unsupported proof; the empirical candidate-generation idea is worth keeping, the NC claim is not. read the letter →

arxiv 2507.11873 v3 pith:5E4WZQUV submitted 2025-07-16 cs.FL cs.PL

Breandan Considine This is my paper · ORCID
classification cs.FLcs.PL MSC 68Q4568Q42
keywords syntaxrepairlanguageintersectionLevenshteinautomatonBar-HillelconstructionCFLreachabilityBrzozowskiderivativeparallelcomputationPythonerrors
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Syntax repair, the paper argues, is best viewed as a question about finite languages rather than about parsing heuristics or trained generators. Given a broken string and a context-free grammar, the repair candidates are exactly the words in the intersection of the grammar's language with an acyclic Levenshtein automaton of radius $\delta_{\max}$; that intersection is finite and contains every valid repair within the edit radius and nothing else. The paper establishes that nonemptiness of this intersection is decidable in polylogarithmic parallel time by recasting the classic grammar-automaton intersection construction as matrix exponentiation over grammar-indexed sets of derivations, and it gives a Brzozowski-derivative decoder that enumerates or samples from the intersection without rejection sampling. On a benchmark of Python syntax errors, the resulting implementation, Tidyparse, constructs the candidate spaces in seconds and, after a learned reranking step, outperforms two neural baselines at recovering the human repair.

What carries the argument

The core mechanism is a matrix whose $(p,r,F)$ entry records, as a set of partial derivations or as a regular expression, that nonterminal $F$ can span the automaton path from state $p$ to state $r$. The operation $\oplus$ unions entries for the same nonterminal, and $\otimes$ combines entries according to a binary production $F\to G\,I$; iterating $M\mapsto M\oplus(M\otimes M)$ is the classical grammar-automaton product construction in matrix form, equivalent to CFL reachability. Because the automaton is acyclic, $M$ is nilpotent, so the full fixpoint is written as a finite matrix exponential. The paper's Levenshtein automaton is the second load-bearing object: a variant of the standard edit automaton that is acyclic, free of epsilon transitions, and symbolic, using predicates on input characters so that an infinite alphabet needs no explicit arc per symbol. The third mechanism is the Brzozowski derivative, which quotients the constructed regular expression by a prefix and thereby generates witnesses one symbol at a time.

What would settle it

Take a small grammar and acyclic automaton for which the root-split product fails associativity—for example productions $S\to A B$ and $B\to C D$ with a state triple where $(M\otimes M)\otimes M$ and $M\otimes(M\otimes M)$ assign different nonterminal entries—and compare the exponentiation-by-squaring parse chart against the naive fixpoint; any discrepancy with a witness string accepted by one and not the other refutes Theorem 3.1. Separately, enumerate all strings within distance $\delta_{\max}$ of a short fixed string and check that the symbolic Levenshtein automaton accepts exactly that set.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.1: for any context-free grammar $\tau$ and acyclic NFA $\mathcal{A}$ with state set $Q$ and grammar nonterminals $N$, there is a decision procedure for $L(\tau)\cap L(\mathcal{A})\neq\emptyset$ requiring $O(\log^2|Q|+\log|Q|\,|N|)$ parallel time with $O(|Q|^2|N|)$ PRAM processors. The argument works by ordering the acyclic automaton topologically, encoding every possible derivation as a strictly upper triangular matrix $M$ over grammar-indexed sets, and computing the fixpoint $M\oplus M^2\oplus\cdots$ by exponentiation by squaring. Applied to the paper's symbolic, cycle-free Levenshtein automaton, the same construction yields a regular expression for $L(\tau)\cap L_{\mathrm{lev}}(f,\delta_{\max})$, a finite language that the paper claims contains all and only valid repairs within $\delta_{\max}$ edits. The paper then separates exact admissibility from naturalness: the intersection language is decoded with Brzozowski derivatives, and the decoded candidates are reranked by a learned model.

Load-bearing premise

The load-bearing premise is that the matrix operation that combines parse entries by splitting at a root production behaves like ordinary multiplication, so exponentiation by squaring reaches the same fixpoint as step-by-step iteration; the paper also assumes the symbolic edit automaton recognizes exactly the strings within the chosen edit radius.

Editorial extensions

If this is right

  • If Theorem 3.1 is correct, bounded repairability for any context-free language is inherently parallelizable, so the same candidate construction can run on GPUs and multicore CPUs.
  • The finite intersection language is decoded directly, so no rejection sampling is needed to guarantee that every emitted repair is grammatically valid.
  • Because the candidate set is complete, a cheap n-gram decoder followed by a reranker can surface repairs that single-shot neural models miss.
  • The paper's Precision@10 results match the much larger candidate set of a strong neural baseline, suggesting that enumerating nearby valid strings matters more than generating one probable string.
  • The same construction applies to any acyclic automaton, so recognition, completion, and repair are unified as instances of one intersection problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implication the paper leaves implicit: if the intersection pipeline is as general as claimed, the same machinery could rank grammar-constrained suggestions for code completion, template filling, and even structured data repair, since those are all intersections of a grammar with a finite description of allowed strings.
  • The complexity result rests on treating the root-split product as an associative operation; a natural testable extension is to identify grammar subclasses, such as visibly pushdown grammars, where associativity provably holds and the polylog bound is unconditional.
  • The paper conditions decoding only on the candidate prefix; conditioning the n-gram or reranker on the broken source and the parser's error message is a direct next step that could improve ranking without changing the completeness guarantee.
  • A weighted Levenshtein automaton with edit-type probabilities on transitions would fold ranking into the construction itself, connecting the paper's exact-language approach to probabilistic grammar intersection.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper formalizes bounded syntax repair as the intersection of a context-free grammar with a Levenshtein ball represented by an acyclic automaton. It proposes a matrix-based CYK-style fixpoint (Algorithms 1–3) to decide nonemptiness and to construct a regular expression for the intersection language, claims a polylogarithmic parallel-time decision procedure (Theorem 3.1), and decodes candidates with an n-gram model plus a transformer reranker (Algorithm 4). The empirical section reports Precision@k results on a StackOverflow Python syntax-repair dataset against Seq2Parse and BIFI, together with ablations and latency measurements.

Significance. The formalization itself—CFL ∩ Levenshtein ball—is a natural way to separate exact admissibility from probabilistic ranking, and the artifact plus the large-scale evaluation are concrete strengths. The exact language-volume computation via the transfer matrix in §5.4 is also a useful technique. If the polylogarithmic parallel-time theorem and the exact Levenshtein-automaton construction were correct, the paper would be a substantial contribution. However, the central theorem is false as stated, and the automaton equivalence is unproved, so the theoretical pillars of the manuscript do not support its main advertised claims. The empirical pipeline may still be of interest, but the paper's core contribution as presented is not established.

major comments (3)
  1. [§3, Theorem 3.1, Eq. (7)–(9), Algorithm 2] The proof of Theorem 3.1 is invalid because the operation ⊗ of Eq. (7) is not associative, and the exponentiation-by-squaring recurrence in Eq. (9) and Algorithm 2 therefore does not compute the intended fixpoint. For example, ((u⊗v)⊗w)_F witnesses a derivation whose root production is F→HJ with H→GI, whereas (u⊗(v⊗w))_F witnesses F→GH with H→IJ; these are different parse shapes. The failure is load-bearing: take the CNF grammar A_1→a, A_i→A_{i-1}A_1 for i=2..n, S→A_nB, and the acyclic automaton accepting exactly a^n b. Under the stated recurrence Γ_{t+1}=Γ_t ∪ Γ_t^2, A_i first appears in round i−1 and S first appears in round n; after about dlog2(|Q||N|) rounds the procedure returns "empty" for a nonempty intersection. Thus the polylogarithmic parallel-time claim and the completeness guarantee for the repair set are unsupported. Since CFL membership is the special case of a single-word acyclic automaton, a correct version of this theorem would place CFL recognition in NC and hence would prove P=NC, which is an extraordinary consequence that the proof does not address.
  2. [§4.3 and Fig. 3] The Levenshtein automaton construction is asserted to recognize exactly L_!(f, δmax), but no correctness proof is provided, and the rules as stated are internally unclear. The deletion rule (i−1,j) --f_i--> (i,j) is labeled by a terminal f_i and therefore appears to consume an input symbol, which is a match transition rather than a deletion; the "skip connections" intended to represent consecutive deletions are not given a precise semantic definition, and the accepting-state predicate "Done" is never defined (the line after the inference rules is garbled). Because the paper's core object is the finite language L(G) ∩ L_!(f, δmax), the claimed "all and only repairs" property is not established. At minimum, a formal equivalence proof against the standard definition of the Levenshtein ball is required.
  3. [§5.3–§5.4 and Algorithm 4] The paper correctly notes in Lemma 5.2 that ambiguity of the Levenshtein automaton causes the same repair to be counted multiple times, and §5.4 gives a determinization procedure for exact counting of distinct repairs. However, Algorithm 4 decodes the regular expression produced by Algorithm 3, not the minimized DFA constructed in §5.4. Consequently, the candidate-sampling distribution used in the experiments remains biased toward ambiguous repairs, which is precisely the pernicious bias identified in §5.3. The text should either integrate disambiguation into the decoder or explain why the ambiguity bias does not affect the reported Precision@k results.
minor comments (5)
  1. [Abstract and §1] The sentence "This approach leverages the classic Bar-Hillel construction ... and yielding a highly parallel decision procedure" contains a grammatical error; "and yielding" should be "yielding" or "and yields".
  2. [§2, Definition 2.2] The typesetting of the Brzozowski derivative rules is garbled (e.g., the derivative operator appears as "m0" and the nullability function as "X"), making Definition 2.2 difficult to read; these equations should be typeset cleanly.
  3. [§7.1 and Fig. 16] The choice of δmax as the smallest radius making the intersection nonempty does not guarantee that the true repair is inside the intersection; Fig. 16 shows 607 of 2,238 test repairs are not ranked because the true repair lies outside the computed set. The paper should clarify how these cases are treated in the Precision@k denominator and whether the reported accuracy is therefore conditional on the true repair being within the discovered radius.
  4. [§9 and references] The text cites "Koutrus and Deep" and "Schulz and Stoyan", but the reference list gives "Koutris and Deep" and "Schulz and Mihov"; the in-text citations should match the bibliography.
  5. [§5.2, Eq. (14)] The disjunction case of the enum function is confusingly written, with a nested min(1, ...) expression that is not explained; this makes the claimed bijection between trees and integers hard to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the repair-set construction is a definitional intersection, the Levenshtein automaton is an independently checkable construction, and the empirical ranking is standard train/test evaluation.

full rationale

I walked the derivation chain and found no step in which a claimed prediction or first-principles result reduces by construction to its own inputs. The central object is the finite language L(tau) intersect L_lev(f, delta_max), defined as the set of valid strings within a fixed edit radius; this is an explicit construction rather than a fitted quantity, and the paper does not tune any parameter against the ground-truth repair. The symbolic Levenshtein automaton of Section 4.3 is presented as a concrete transition system, with its correctness asserted as equivalence to the standard Schulz-Mihov construction; that is a checkable external claim, not a self-referential definition, and the paper even notes that acyclic variants avoid epsilon-arcs. The CYK-style matrix closure in Section 4.1 is openly identified as the textbook CYK algorithm in linear-algebraic notation, so there is no renaming of a known result presented as a new prediction. The main theoretical weakness is Theorem 3.1: the exponentiation-by-squaring recurrence over a non-associative grammar-indexed product appears unsupported, and the resulting polylogarithmic PRAM claim is at risk. However, an incorrect or unproved algebraic step is a correctness and complexity concern, not circularity: the theorem's conclusion is not equivalent to its assumptions by definition. The empirical section follows a conventional disjoint train/test protocol on StackOverflow repairs, and the paper explicitly reports 607 test cases where the true repair was not contained in the language intersection, which would be impossible if the edit radius had been fitted to the ground truth. No load-bearing self-citations, imported uniqueness theorems, or fitted-input-called-prediction steps are present. I therefore assign a circularity score of 0.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The core theory is mostly self-contained but rests on two unproved construction claims: the symbolic Levenshtein automaton exactly characterizing the edit ball, and the parse-chart recurrence computing the full CFL intersection. In the evaluation, several thresholds (length, edit distance, top-k, timeout) shape the reported results.

free parameters (5)
  • Edit radius delta_max = smallest nonempty intersection; <=3 in evaluation
    Chosen per query; controls candidate set size and cost. Not fitted to the human repair, but affects completeness.
  • Markov order c of decoder = 4
    The 4-gram model is used for decoding and confounder sampling; no ablation of n-gram order is reported.
  • Reranker temperature tau = 0.1
    Appendix C lists temperature 0.1; chosen by hand.
  • Top-k thresholds = 1000 sampled, top-10 reported
    Decoder returns up to 10^3 candidates, reranker uses top-10; these engineering choices define the empirical results.
  • Dataset filters = |f| < 80 tokens, Levenshtein distance < 4
    Applied before evaluation; defines the feasible subset for the headline claims.
assumptions (5)
  • standard math Every CFG can be rewritten to Chomsky Normal Form without changing the language.
    Invoked in Section 2 and required by Algorithms 2 and 3.
  • ad hoc to paper The symbolic acyclic Levenshtein automaton in Section 4.3 recognizes exactly the set of strings within Levenshtein distance delta_max of the broken string, and does so without epsilon transitions.
    The correctness of the 'all and only repairs' claim depends on this construction, but no formal proof is given.
  • ad hoc to paper The parse-chart recurrence M_{n+1} = M_n union (M_n tensor M_n), with tensor defined by a single binary production at the root, computes every nonterminal derivable from each automaton state pair.
    This is the core correctness lemma behind Theorem 3.1; associativity of the grammar-indexed product is assumed implicitly in Equations 7 to 9.
  • standard math The PRAM model permits O(log^2 |Q|) topological sorting and concurrent memory access without locks, as cited from Dekel et al.
    Used in Theorem 3.1 to justify the parallel time bound.
  • domain assumption The StackOverflow corpus used in Section 7 is representative and the train/test split does not leak repairs.
    The empirical claim depends on this; no data or split is released.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Syntax Repair as Language Intersection." pith.science (2026). https://pith.science/paper/5E4WZQUV

@misc{pith2026250711873,
  author       = {Pith},
  title        = {Pith review of: Syntax Repair as Language Intersection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5E4WZQUV}},
  note         = {Machine review of arXiv:2507.11873}
}
read the original abstract

Syntax repair can be viewed as a question about finite languages: given an invalid string and a grammar, which nearby strings are syntactically valid? We formalize bounded syntax repair as the intersection of a context-free language with an acyclic Levenshtein automaton, obtaining a finite language that contains all and only repairs within a chosen edit radius. This approach leverages the classic Bar-Hillel construction for CFL-regular intersection, and specializes it to acyclic automata, and yielding a highly parallel decision procedure for deciding repairability. We then show how Brzozowski derivatives support fast incremental enumeration from this intersection, separating exact admissibility from probabilistic ranking. Experiments on Python syntax errors demonstrate the resulting candidate spaces are practical to construct and substantially improve repair accuracy when used as a grammar-constrained search space.

Figures

Figures reproduced from arXiv: 2507.11873 by the authors.

Figure 1
Figure 1. Our algorithm first constructs an automaton representing all strings within a certain edit distance. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. CFL intersection with the local edit region around a broken code snippet, where 3⇤ = 3 is the language edit distance (LED). Given a lexical representation of a broken computer program f : and a grammar ⌧, our goal is to find every valid string f consistent with the grammar ⌧ and within a certain edit distance, 3. Consider the language of nearby strings: if intersected with the language of grammatically valid program… view at source ↗
Figure 3
Figure 3. Levenshtein NFA recognizing L￾ !(f : ⌃5, 3) ￾ . As the original construction defined by Schultz and Mihov [48] contains cycles and Y￾transitions, we propose a variant which is Y￾free and acyclic. Furthermore, we adopt a sym￾bolic form that supports infinite alphabets and simplifies the description to follow. Illustrated in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (20 more)
Figure 4
Figure 4. Figure 4: Simple Levenshtein automaton. @0,1 @1,1 @2,1 @3,1 @0,0 @1,0 @2,0 @3,0 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 6
Figure 6. Figure 6: Adjacency and reachability matrix. "0 @00 @01 @10 @11 @20 @21 @30 @31 @00 ( ⇤ ￾ ⇤ ! ⇤' ⌅ ( ⇤ ￾ ⇤ ! ⌅' ⇤ ( ⇤ ￾ ⇤ ! ⇤' ⌅ ( ⇤ ￾ ⇤ ! ⇤' ⇤ ( ⇤ ￾ ⇤ ! ⇤' ⌅ ( ⇤ ￾ ⇤ ! ⇤' ⇤ ( ⇤ ￾ ⇤ ! ⇤' ⇤ @01 ⇤⇤⇤⇤ ⇤⇤⌅⇤ ⇤⇤⇤⇤ ⇤⇤⇤⇤ ⇤⇤⇤⇤ ⇤⇤⇤⇤ @10 ⇤⇤⌅⇤ ⇤⇤⇤⌅ ⇤⇤⌅⇤ ⇤⇤⇤⇤ ⇤⇤⇤⌅ @11 ⇤⇤⇤⇤ ⇤⇤⇤⌅ ⇤⇤⇤⇤ ⇤⇤⇤⇤ @20…
Figure 7
Figure 7. Figure 7: Initial parse chart configuration. "1 @00 @01 @10 @11 @20 @21 @30 @31 @00 ( ⇤ ￾ ⇤ ! ⇤' ⌅ ( ⇤ ￾ ⇤ ! ⌅' ⇤ ( ⇤ ￾ ⇤ ! ⇤' ⌅ ( ⌅ ￾ ⇤ ! ⇤' ⇤ ( ⇤ ￾ ⇤ ! ⇤' ⌅ ( ⇤ ￾ ⌅ ! ⇤' ⇤ ( ⌅ ￾ ⇤ ! ⇤' ⇤ @01 ⇤⇤⇤⇤ ⇤⇤⌅⇤ ⇤⇤⇤⇤ ⌅⇤⇤⇤ ⇤⇤⇤⇤ ⇤⌅⇤⇤ @10 ⇤⇤⌅⇤ ⇤⇤⇤⌅ ⌅⇤⌅⇤ ⇤⇤⇤⇤ ⌅⌅⇤⌅ @11 ⇤⇤⇤⇤ ⇤⇤⇤⌅ ⇤⇤⇤⇤ ⇤⇤⇤⇤ @20…
Figure 8
Figure 8. Figure 8: Final parse chart configuration. ∨ ∨ ∨ · · · · · {Σ₀} {Σ₁} {Σ₀} {Σ₁} {Σ₀} {Σ₁} {Σ₀} · · {Σ₁} {Σ₀} {Σ₁} · · · · {Σ₀} {Σ₁} {Σ₀} {Σ₁} {Σ₀} · · {Σ₁} {Σ₀} {Σ₁} [PITH_FULL_IMAGE:figures/full_fig_p009_8.png]
Figure 9
Figure 9. Figure 9: Regular expression denoting L(⌧\). As a concrete example, suppose we have the string, f : = ()) and wish to balance the parentheses. We will initially have the Levenshtein automaton, ￾, depicted in [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]
Figure 10
Figure 10. Figure 10: FSA for L￾ !(()), 1) ￾ \ L(⌧0 ) (a) with or (b) without _-merging, and then (c) post-minimization. Since L(⌧\) is necessarily finite, we can infer that the corresponding DFA is acyclic and thus representable as an upper triangular adjacency matrix under a topological …
Figure 11
Figure 11. Figure 11: Transformer data encoding. More concretely, we depict a single instance of the training data in [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]
Figure 12
Figure 12. Figure 12: Repair statistics across the StackOverflow dataset, of which Tidyparse can handle about half in under [PITH_FULL_IMAGE:figures/full_fig_p017_12.png]
Figure 13
Figure 13. Figure 13: Language volume versus snippet length and edit distance for Python repairs. For an intuition about the size of the language intersections involved in syntax repair, volumetric analysis will be helpful, particularly in understand￾ing the influence of snippet length and…
Figure 14
Figure 14. Figure 14: Probability of the first recommendation matching the true repair for Tidyparse, Seq2Parse and BIFI [PITH_FULL_IMAGE:figures/full_fig_p018_14.png]
Figure 15
Figure 15. Figure 15: Probability of the true repair being in the first [PITH_FULL_IMAGE:figures/full_fig_p018_15.png]
Figure 16
Figure 16. Figure 16: Outcomes in the repair pipeline. We present a Sankey diagram of the Tidyparse repair pipeline in [PITH_FULL_IMAGE:figures/full_fig_p018_16.png]
Figure 17
Figure 17. Figure 17: 4-gram repairs. 4-gram Precision@1000 is an upper bound on Tidyparse Precision@k, since the latter [PITH_FULL_IMAGE:figures/full_fig_p019_17.png]
Figure 18
Figure 18. Figure 18: Observed improvement in repair rank with and without the transformer reranker. We can quantify the ranking improvement by comparing CDFs of the true repair’s rank across the test set of human repairs, before and after rerank￾ing the top-103 sampled repairs ( [PITH_FU…
Figure 19
Figure 19. Figure 19: End-to-end repair timings. As shown in [PITH_FULL_IMAGE:figures/full_fig_p019_19.png]
Figure 20
Figure 20. Figure 20: Lev(|f|=6, ￾=1) automaton, adjacency and reachability matrix. q_00/02 q_01/02 q_02/02 q_03/02 q_04/02 q_05/02 q_06/02 q_00/01 q_01/01 q_02/01 q_03/01 q_04/01 q_05/01 q_06/01 q_00/00 q_01/00 q_02/00 q_03/00 q_04/00 q_05/00 q_06/00 [PITH_FULL_IMAGE:figures/full_fig_p02…
Figure 21
Figure 21. Figure 21: Lev(|f|=6, ￾=2) automaton, adjacency and reachability matrix. q_00/03 q_01/03 q_02/03 q_03/03 q_04/03 q_05/03 q_06/03 q_00/02 q_01/02 q_02/02 q_03/02 q_04/02 q_05/02 q_06/02 q_00/01 q_01/01 q_02/01 q_03/01 q_04/01 q_05/01 q_06/01 q_00/00 q_01/00 q_02/00 q_03/00 q_04/0…
Figure 22
Figure 22. Figure 22: Lev(|f|=6, ￾=3) automaton, adjacency and reachability matrix. q_00/04 q_01/04 q_02/04 q_03/04 q_04/04 q_05/04 q_06/04 q_00/03 q_01/03 q_02/03 q_03/03 q_04/03 q_05/03 q_06/03 q_00/02 q_01/02 q_02/02 q_03/02 q_04/02 q_05/02 q_06/02 q_00/01 q_01/01 q_02/01 q_03/01 q_04/0…
Figure 23
Figure 23. Figure 23: Lev(|f|=6, ￾=4) automaton, adjacency and reachability matrix [PITH_FULL_IMAGE:figures/full_fig_p028_23.png]
Figure 24
Figure 24. Figure 24: Levenshtein NFA before and after prefix and suffix pruning. [PITH_FULL_IMAGE:figures/full_fig_p029_24.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 37 canonical work pages

  1. [5]

    [7]Yehoshua Bar-Hillel, Micha Perles, and Eli Shamir

    Structured denoising diffusion models in discrete state-spaces.Advancesinneuralinformationprocessingsystems34 (2021), 17981–17993. [7]Yehoshua Bar-Hillel, Micha Perles, and Eli Shamir

    work page 2021

  2. [10]

    InProceedingsof the29thACMjointmeetingonEuropeansoftwareengineeringconferenceandsymposiumonthefoundationsof softwareengineering

    Empirical study of transformers for source code. InProceedingsof the29thACMjointmeetingonEuropeansoftwareengineeringconferenceandsymposiumonthefoundationsof softwareengineering. 703–715. [14]DmitryChistikov,RupakMajumdar,andPhilippSchepper.2022. SubcubiccertificatesforCFLreachability. Proceedings oftheACMonProgrammingLanguages 6, POPL (2022), 1–29. [15]No...

    work page 2022

  3. [12]

    Don't Panic! Better, Fewer, Syntax Errors for LR Parsers

    Don’t Panic! Better, Fewer, Syntax Errors for LR Parsers.arXivpreprint arXiv:1804.07133 (2018). [18]Dawn Drain, Chen Wu, Alexey Svyatkovskiy, and Neel Sundaresan

    work page Pith review arXiv 2018

  4. [13]

    InProceedingsofthe5thACMSIGPLANInternationalSymposiumonMachineProgramming

    Generating bug-fixes using pretrained transformers. InProceedingsofthe5thACMSIGPLANInternationalSymposiumonMachineProgramming. 1–8. [19]Philippe Duchon, Philippe Flajolet, et al.2004. Boltzmann samplers for the random generation of combinatorial structures.Combinatorics,ProbabilityandComputing 13, 4-5 (2004), 577–625. [20]Jay Earley

    work page 2004

  5. [23]

    [34]Lillian Lee

    The fine-grained complexity of CFL reachability.ProceedingsoftheACM onProgrammingLanguages 7, POPL (2023), 1713–1739. [34]Lillian Lee

    work page 2023

  6. [25]

    [36]João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, et al.2025

    Sequential monte carlo steering of large language models using probabilistic programs.arXivpreprintarXiv:2306.03081 (2023). [36]João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, et al.2025. Syntactic and semantic control of large language models via sequential monte car...

    arXiv 2023

  7. [28]

    [41]Alexander Okhotin

    The language intersection problem for non-recursive context-free grammars.InformationandComputation 192, 2 (2004), 172–184. [41]Alexander Okhotin

    work page 2004

  8. [30]

    InProceedingsofthe17thConferenceoftheEuropeanChapter oftheAssociationforComputationalLinguistics, Andreas Vlachos and Isabelle Augenstein (Eds.)

    On the In- tersection of Context-Free and Regular Languages. InProceedingsofthe17thConferenceoftheEuropeanChapter oftheAssociationforComputationalLinguistics, Andreas Vlachos and Isabelle Augenstein (Eds.). Association for Computational Linguistics, Dubrovnik, Croatia, 737–749.https://doi.org/10.18653/v1/2023.eacl-main.52 [43]Tikhon Pshenitsyn

    work page doi:10.18653/v1/2023.eacl-main.52

Show all 42 references
  1. [31]

    [44]Thomas Reps

    First-Order ILL and Hypergraph Languages.arXivpreprintarXiv:2502.05816 (2025). [44]Thomas Reps

    2025 arXiv

  2. [33]

    [47]Arto Salomaa

    Seq2Parse: neurosymbolic parse error repair.ProceedingsoftheACMonProgrammingLanguages 6, OOPSLA2 (2022), 1180–1206. [47]Arto Salomaa. 1973.Formallanguages. Academic Press, New York. 59–61 pages. [48]Klaus U Schulz and Stoyan Mihov

    2022

  3. [34]

    [49]Caleb Stanford, Margus Veanes, and Nikolaj Bjørner

    Fast string correction with Levenshtein automata.InternationalJournalon DocumentAnalysisandRecognition 5 (2002), 67–85. [49]Caleb Stanford, Margus Veanes, and Nikolaj Bjørner

    2002

  4. [36]

    [52]Leslie G Valiant

    Improving LLM code generation with grammar augmentation.arXivpreprintarXiv:2403.01632 (2024). [52]Leslie G Valiant

    2024 arXiv

  5. [38]

    [54]Gail Weiss, Yoav Goldberg, and Eran Yahav

    RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted Lookarounds.ProceedingsoftheACMonProgrammingLanguages9, POPL (2025), 1–32. [54]Gail Weiss, Yoav Goldberg, and Eran Yahav

    2025

  6. [39]

    [56]Alexander William Wong, Amir Salimi, Shaiful Chowdhury, and Abram Hindle

    Efficient guided generation for LLMs.arXivpreprintarXiv:2307.09702(2023). [56]Alexander William Wong, Amir Salimi, Shaiful Chowdhury, and Abram Hindle

    2023 arXiv

  7. [40]

    [58]Michihiro Yasunaga and Percy Liang

    Masked hard-attention transformers recognize exactly the star-free languages.AdvancesinNeuralInformationProcessingSystems 37 (2024), 10202–10235. [58]Michihiro Yasunaga and Percy Liang

    2024

  8. [41]

    InInternational ConferenceonMachineLearning

    Break-it-fix-it: Unsupervised learning for program repair. InInternational ConferenceonMachineLearning. PMLR, 11941–11952. [59]QirunZhangandZhendongSu.2017. Context-sensitivedata-dependenceanalysisvialinearconjunctivelanguagereach- ability. InProceedingsofthe44thACMSIGPLANSymp...

    2017

  9. [42]

    Breandan Considine A LEVENSHTEIN TOPOLOGY AND MATRICES These are useful for visually checking different implementations

    OrdinalFix: Fixing Compilation Errors via Shortest-Path CFL Reachability.arXivpreprintarXiv:2309.06771 (2023). Breandan Considine A LEVENSHTEIN TOPOLOGY AND MATRICES These are useful for visually checking different implementations. q_6/1q_5/1q_4/1q_3/1q_2/1q_1/1q_0/1 q_6/0q_5/...

    2023 arXiv

  10. [1959]

    [16]EliezerDekel,DavidNassimi,andSartajSahni.1981

    On certain formal properties of grammars.Informationandcontrol 2, 2 (1959), 137–167. [16]EliezerDekel,DavidNassimi,andSartajSahni.1981. Parallelmatrixandgraphalgorithms. SIAMJournaloncomputing 10, 4 (1981), 657–675. [17]Lukas Diekmann and Laurence Tratt

    1959

  11. [1961]

    SprachtypologieundUniversalienforschung 14 (1961), 143–172

    On formal properties of simple phrase structure grammars. SprachtypologieundUniversalienforschung 14 (1961), 143–172. [8]Janusz A Brzozowski

    1961

  12. [1962]

    [25]Joshua Goodman

    Two families of languages related to ALGOL.JournaloftheACM (JACM) 9, 3 (1962), 350–371. [25]Joshua Goodman

    1962

  13. [1963]

    [31]Aleksandra Istomina, Semyon Grigorev, and Ekaterina Shemetova

    An Error-Correcting Parse Algorithm.Commun.ACM 6, 11 (nov 1963), 669–673. [31]Aleksandra Istomina, Semyon Grigorev, and Ekaterina Shemetova

    1963

  14. [1964]

    [10]Janusz A

    Derivatives of regular expressions.JournaloftheACM(JACM) 11, 4 (1964), 481–494. [10]Janusz A. Brzozowski and Ernst Leiss

    1964

  15. [1970]

    [21]Conal Elliott

    An efficient context-free parsing algorithm.Commun.ACM 13, 2 (1970), 94–102. [21]Conal Elliott

    1970

  16. [1972]

    SIAMJ.Comput

    A minimum distance error-correcting parser for context-free languages. SIAMJ.Comput. 1, 4 (1972), 305–312. [3]Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton

    1972

  17. [1975]

    General context-free recognition in less than cubic time.Journalofcomputerandsystem sciences 10, 2 (1975), 308–315.http://people.csail.mit.edu/virgi/6.s078/papers/valiant.pdf [53]Ian Erik Varatalu, Margus Veanes, and Juhan Ernits

    1975

  18. [1980]

    [11]David Chiang

    On equations for regular languages, finite automata, and sequential networks.TheoreticalComputerScience 10, 1 (1980), 19–35. [11]David Chiang

    1980

  19. [1983]

    Uniform random generation of strings in a context-free language.SIAMJ. Comput. 12, 4 (1983), 645–655. [29]Liang Huang and David Chiang

    1983

  20. [1996]

    [6]Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg

    Partial derivatives of regular expressions and finite automaton constructions.Theoretical ComputerScience 155, 2 (1996), 291–319. [6]Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg

    1996

  21. [1998]

    [45]Itiroo Sakai

    Program analysis via graph reachability.Informationandsoftwaretechnology (1998). [45]Itiroo Sakai

    1998

  22. [1999]

    [26]Dick Grune and Ceriel J

    Semiring parsing.ComputationalLinguistics 25, 4 (1999), 573–606. [26]Dick Grune and Ceriel J. H. Jacobs. 2008.ParsingasIntersection. Springer New York, New York, NY, 425–442. [27]Marton Havasi, Brian Karrer, Itai Gat, and Ricky TQ Chen

    1999

  23. [2001]

    [42]Clemente Pasti, Andreas Opedal, Tiago Pimentel, Tim Vieira, Jason Eisner, and Ryan Cotterell

    Conjunctive grammars.JournalofAutomata,LanguagesandCombinatorics (2001). [42]Clemente Pasti, Andreas Opedal, Tiago Pimentel, Tim Vieira, Jason Eisner, and Ryan Cotterell

    2001

  24. [2002]

    Fast context-free grammar parsing requires fast boolean matrix multiplication.JournaloftheACM (JACM) 49, 1 (2002), 1–15.https://arxiv.org/pdf/cs/0112018.pdf [35]Alexander K Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash K Mansinghka

    2002 arXiv

  25. [2004]

    Syntax Repair as Language Intersection [33]Paraschos Koutris and Shaleen Deep

    The set constraint/CFL reachability connection in practice.ACMSigplanNotices 39, 6 (2004), 207–218. Syntax Repair as Language Intersection [33]Paraschos Koutris and Shaleen Deep

    2004

  26. [2007]

    [12]David Chiang, Peter Cholak, and Anand Pillay

    Hierarchical phrase-based translation.computationallinguistics 33, 2 (2007), 201–228. [12]David Chiang, Peter Cholak, and Anand Pillay

    2007

  27. [2011]

    [39]Ilia Muravev and Semyon Grigorev

    Parsing with derivatives: a functional pearl.ACMsigplan notices 46, 9 (2011), 189–195. [39]Ilia Muravev and Semyon Grigorev

    2011

  28. [2018]

    A survey of machine learning for big code and naturalness.ACMComputingSurveys(CSUR) 51, 4 (2018), 1–37.https://arxiv.org/pdf/1709.06182.pdf [4]Miltiadis Allamanis, Henry Jackson-Flux, and Marc Brockschmidt

    2018 arXiv

  29. [2019]

    Generalized Convolution and Efficient Language Recognition (Extended version). (2019). [22]David Eppstein. 2014.:-best enumeration.arXivpreprintarXiv:1412.5075 (2014). [23]Philippe Flajolet. 2009.AnalyticCombinatorics. Cambridge University Press. [24]Seymour Ginsburg and H Gordon Rice

    2019 arXiv

  30. [2021]

    AdvancesinNeuralInformationProcessingSystems 34 (2021), 27865–27876.https://arxiv.org/pdf/2105.12787.pdf [5]Valentin Antimirov

    Self-supervised bug detection and repair. AdvancesinNeuralInformationProcessingSystems 34 (2021), 27865–27876.https://arxiv.org/pdf/2105.12787.pdf [5]Valentin Antimirov

    2021 arXiv

  31. [2022]

    [38]Matthew Might, David Darais, and Daniel Spiewak

    Saturated transformers are constant-depth threshold circuits.TransactionsoftheAssociationforComputationalLinguistics 10 (2022), 843–856. [38]Matthew Might, David Darais, and Daniel Spiewak

    2022

  32. [2023]

    [32]John Kodumal and Alex Aiken

    Fine-grained reductions around CFL- reachability.arXivpreprintarXiv:2306.15967 (2023). [32]John Kodumal and Alex Aiken

    2023 arXiv

  33. [2024]

    [51]Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh

    What formal languages can transformers express? a survey.TransactionsoftheAssociationforComputationalLinguistics 12 (2024), 543–561. [51]Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh

    2024

  34. [2025]

    arXivpreprintarXiv:2506.09018 (2025)

    Edit Flows: Flow Matching with Edit Operations. arXivpreprintarXiv:2506.09018 (2025). [28]Timothy Hickey and Jacques Cohen

    2025

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.