acceptodds
Under review as a conference paper at ICLR 2027

On Graph Transformer Expressivity: A Monadic Second-Order Perspective

Abstract

We characterize the expressive power of graph transformers by showing that transformers express monadic second-order logic (MSO) for bounded-treewidth graphs. MSO is a powerful logic for graph-related tasks, as it allows to decide many problems for graphs with bounded treewidth in linear fixed-parameter-tractable (FPT) time, such as connectivity, planarity, and -colorability for fixed . The expressive power of general transformers is often quantified by their ability to simulate certain formal languages in the context of natural language processing. In this paper, we focus on graph representation learning and MSO: We show that transformers with -precision and average-hard attention can produce distinct embeddings for bounded-treewidth graphs that differ in MSO-definable properties in near-linear FPT time if the tree decomposition is given as input, and in near-cubic FPT time if the tree decomposition is not given. We establish this expressivity lower bound by showing that transformers have sufficient expressive power to compute bounded-width tree decompositions and simulate tree automata for graphs equipped with simple structural encodings. Our proofs are constructive and provide upper bounds on the required size of the transformers, scaling with the size of the input graph, the treewidth as well as the length of the MSO formula.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Transformers, graphs, expressivity

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_4vd9OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the expressive power of graph transformers. Specifically, the work shows that graph transformers with 'basic' structural encodings can express MSO in the non-uniform setting and over graphs of bounded treewidth. The resulting graph transformers are shown to run in FPT time O(n^3log(n)), and FPT time O(nlog(n)) when a 'nice' and 'balanced' tree decomposition is given.

Critical strengths
  1. Showing that graph transformers can compute tree decompositions in fixed parameter tractable time is a novel contribution and argues for the 'naturalness' of the MSO lower-bound.

  2. The notion of 'expressing a property' is strong. I.e. there is some constant c for which f(G) = c iff G has property P.

  3. The paper is candid regarding its limitations.

Critical weaknesses
  1. The structural encoding is quite strong in that it encodes the whole graph structure. Having this combined with the non-uniform setting, it leaves the question whether obtaining an MSO lower-bound is surprising as the option of 'memorizing' all of the finitely many graph is seemingly left possible.

  2. The tokenization of graphs not being permutation invariant, whilst seemingly not affecting the characterisation, raises the question to whether this encoding is natural.

  3. No converse to the expressivity lower-bound is established thus leaving this a partial characterisation.

Suggestions:

  1. Line 068 and other places: it is unclear that 'graph transformers can express MSO in FPT ... time' is referring to the runtime of the graph transformer.

  2. Line 195: the conjunct (X_i v \wedge X_i w) should be negated.

  3. It would be interesting to see if a graph transformer can be trained to compute tree decompositions.

Questions for authors
  1. Is it not the case that, in the non-uniform setting with the assumed structural encoding, graph transformers can capture all graph properties (or at least some superset of MSO-properties)? If so, is the 'connection to MSO' argument based solely on fixed parameter tractability?

  2. To what extent does the characterisation depend on the specific structural encoding? Is any characterisation known for, e.g. spectral or random walk encodings?

  3. Less important than the other question, but it would be nice to know what is preventing a uniform characterisation?

2 comments

We thank the reviewer for their detailed comments, and for highlighting the novelty of our theoretical contributions!

We address each of the weaknesses and questions below.

  1. The structural encoding is quite strong in that it encodes the whole graph structure. Having this combined with the non-uniform setting, it leaves the question whether obtaining an MSO lower-bound is surprising as the option of 'memorizing' all of the finitely many graph is seemingly left possible.

We agree that the encoding provides the full graph structure, deliberately so, to complement Ahvonen et al. (2026), who study graph transformers without structural information. Indeed, in the non-uniform setting, any property of the finitely many graphs of size at most nn can in principle be memorized. However, this requires transformers whose size grows exponentially with nn. Our result is meaningful precisely because, for a fixed MSO formula φ\varphi, the transformer has size polynomial in nn, with a factor g(k,φ)g(k, \varphi) independent of nn. Given a tree decomposition, a looped transformer even has parameter count independent of nn (cf. Theorem 4.5).

2. The tokenization of graphs not being permutation invariant, whilst seemingly not affecting the characterisation, raises the question to whether this encoding is natural.

Our encoding follows Sanford et al. (2024): the graph is serialized as node and edge tokens, as it would be for a standard sequence transformer. This allows us to connect graph transformer expressivity with the sequence-based transformer literature, where such order-dependent encodings are standard. Importantly, the transformer’s output is invariant: all vertex orderings of the same graph are mapped to the same output. Only intermediate objects, such as the tree decomposition, may depend on the ordering. We have clarified this in the revised paper.

3. No converse to the expressivity lower-bound is established thus leaving this a partial characterisation.

Indeed, our results provide a lower bound on expressivity rather than a full characterization. We show that graph transformers with a standard sequence-based encoding can express all MSO-definable properties on bounded-treewidth graphs, and quantify the transformer size required to do so. We consider a full characterization as an interesting direction for future work.

  1. Line 068 and other places: it is unclear that 'graph transformers can express MSO in FPT ... time' is referring to the runtime of the graph transformer.

Thanks for bringing this up, we have added some explanation on the time complexity and made this more explicit throughout the paper.

  1. Line 195: the conjunct (X_i v \wedge X_i w) should be negated.

Thanks for pointing this out, we fixed it.

3. It would be interesting to see if a graph transformer can be trained to compute tree decompositions.

We believe this is outside of the scope of our submission but agree that this would be great follow-up work, thank you for the suggestion!

  1. Is it not the case that, in the non-uniform setting with the assumed structural encoding, graph transformers can capture all graph properties (or at least some superset of MSO-properties)? If so, is the 'connection to MSO' argument based solely on fixed parameter tractability?

Yes, in the non-uniform setting and with our encoding, sufficiently large transformers can express every graph property on graphs of size at most nn, e.g., by memorization, at exponential size. The connection to MSO via automata simulation is therefore not only about which properties are expressible in principle, but about the required resources. For a fixed MSO formula φ\varphi, our construction yields transformers of size polynomial in nn (with a factor g(k,φ)g(k, \varphi) independent of nn) and FPT running time. Our result is thus not intended as a tight characterization, but as a constructive lower bound with explicit time and size requirements.

  1. To what extent does the characterisation depend on the specific structural encoding? Is any characterisation known for, e.g. spectral or random walk encodings?

Our result is specific to the sequence-based encoding with node and edge tokens. Known results for spectral and random-walk encodings typically characterize expressivity via Weisfeiler-Leman variants rather than logics (Black et al., 2024 and Stoll et al., 2025). Whether such encodings suffice for an MSO lower bound is, to our knowledge, an open and interesting question.

  1. Less important than the other question, but it would be nice to know what is preventing a uniform characterisation?

In our construction, the number of layers grows with nn: computing the tree decomposition requires O(nlog⁡n)O(n \log n) layers, and simulating the tree automaton requires O(log⁡n)O(\log n) layers, determined by the depth of the balanced tree decomposition. Given a tree decomposition, our looped construction is already uniform in its parameters: only the number of iterations depends on nn (Theorem 4.5 and Remark A.5). We believe that a uniform constant-depth result is unlikely: constant-depth transformers with logarithmic precision are contained in TC$^0$ (see, e.g., Merrill et al., 2022), whereas some MSO-definable properties, such as having a perfect matching, are L-hard on bounded-treewidth graphs (Das et al., 2013). Thank you for the question, we consider this an interesting direction for future work!

Veeti Ahvonen, Maurice Funk, Damian Heiman, Antti Kuusisto, and Carsten Lutz. Expressive power of graph transformers via logic. AAAI 2026.

Mitchell Black, Zhengchao Wan, Gal Mishne, Amir Nayyeri, and Yusu Wang. Comparing graph transformers via positional encodings. ICML 2024.

Timo Stoll, Luis Müller, and Christopher Morris. Generalizable insights for graph transformers in theory and practice. NeurIPS 2025.

William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated Transformers are Constant-Depth Threshold Circuits. TACL 2022.

Bireswar Das, Samir Datta, Prajakta Nimbhorkar. Log-Space Algorithms for Paths and Matchings in k-Trees. Theory of Computing Systems 2013.

Reviewer_nsnLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the expressivity of transformer models through a novel approach (as far as I have gathered) – using monadic second-order logic on graphs of bounded treewidth. The main theorem, Theorem 4.3, proves the existence of transformer weights for each MSO-definable property that express that property on bounded-treewidth graphs, with time (the paper uses time instead of arithmetic operations/amount of computation) that grows near-cubically with the size of the input graph. The paper uses the idea of FPT (fixed-parameter tractability) properly to allow exponential dependence of this time on k (the minimum possible largest bag size in a valid tree decomposition of a graph, minus one) and gives an O(n log n)-time construction when a nice and balanced tree decomposition of the graph is provided. The proof follows the automata-based approach underlying Courcelle’s theorem: construct a tree decomposition, encode the graph as a labeled tree, then simulate a tree automaton that decides the MSO property. The paper then shows how transformers can implement each stage of this algorithm (with Theorem 4.4 addressing the decomposition construction), together with explicit bounds on the computational resources required.

Critical strengths
  • I find the paper’s framing compelling. Tree decompositions organize graph reasoning into a hierarchy of local computations, creating a natural connection to transformer models’ ability to represent and process structured dependencies. This perspective provides a useful framework for studying transformer expressivity on graphs and offers a promising foundation for further theoretical work.
  • MSO provides a direct connection to well-studied graph properties, such as colorability, connectivity, and Hamiltonicity.
  • The work also builds on earlier connections between transformers and automata, building on earlier transformer simulations of sequence and tree automata to study bounded-treewidth graphs. An important contribution is constructing the tree decomposition within the transformer, together with the claimed FPT resource bounds.
    • The overall strategy behind the near-cubic result is elegant, combining classical graph algorithms and automata theory with more recent transformer simulation techniques.
Critical weaknesses
  • The connection to practical graph learning remains insufficiently established.
    • Although the FPT guarantees provide meaningful theoretical insight, their dependence on treewidth and the chosen MSO property can be very large, and their usefulness for graph families with growing treewidth is unclear. The authors discuss relevant examples and acknowledge these limitations, but the results alone do not establish how broadly the constructions explain the behavior of practical graph transformers.
    • The proposed experimental evaluation, particularly across varying treewidths and model sizes, would strengthen this connection and would have helped assess whether trained models exhibit the capabilities established by the existence results.
  • Novelty relative to known simulation and circuit-complexity results.
    • The novelty relative to existing results needs clarification. Elberfeld et al. (2010) give logspace algorithms for both constructing tree decompositions and deciding MSO properties, while Merrill and Sabharwal (2025b, cited) connect logspace computation to logarithmic-depth padded transformers. This suggests a shallower alternative (although potentially using more tokens). The authors should explicitly state what their construction adds (or saves).
    • Separately, there seem to be parallel algorithms for bounded-treewidth graphs (see Bodlaender & Hagerup, SICOMP 1998). I wonder whether simulating a parallel algorithm would yield a shallower transformer under the same resource constraints.

Despite these weaknesses, I am willing to recommend weak acceptance. I strongly encourage the authors to address the concerns raised above to improve the overall quality of the manuscript.

Minor Comments

  • There seems to be a typo in the MSO_1 formula for 3-colorability negation missing to the right of implies (since we want edges connecting different colored notes). Also adding parenthesis to the logical formulas on the middle of page 4 would definitely help with readability!
Questions for authors
  • Table 1 reports automaton sizes parameterized by cliquewidth, whereas the main construction is parameterized by treewidth. Please clarify these differences and explain how these cliquewidth examples inform the resource requirements of the main treewidth construction.
2 comments

We thank the reviewer for their detailed comments and the constructive suggestions!

We address each of the weaknesses and your question below.

  • Although the FPT guarantees provide meaningful theoretical insight, their dependence on treewidth and the chosen MSO property can be very large, and their usefulness for graph families with growing treewidth is unclear. The authors discuss relevant examples and acknowledge these limitations, but the results alone do not establish how broadly the constructions explain the behavior of practical graph transformers.

Our contribution is theoretical: we give explicit constructions with concrete bounds on transformer size and inference time. These worst-case bounds can be very large, but the automata for many relevant properties are much smaller in practice (Table 1). Whether trained graph transformers learn such solutions is an important question that is beyond the scope of this paper, and we highlight it as future work.

  • The proposed experimental evaluation, particularly across varying treewidths and model sizes, would strengthen this connection and would have helped assess whether trained models exhibit the capabilities established by the existence results.

We agree that an empirical evaluation would be valuable. However, we see our theoretical results as complementary to existing empirical work: they show that the observed capabilities are within the expressive power of the architecture, and provide a possible explanation by which transformers can capture such global properties.

Novelty relative to known simulation and circuit-complexity results.

Relation to Elberfeld et al. (2010) and Merrill & Sabharwal (2025). We thank the reviewer for pointing out this connection, which we had not considered. We agree that combining the logspace algorithms of Elberfeld et al. with the characterization of padded log-looped transformers by Merrill & Sabharwal suggests a different, shallower route to a proof of existence. Making this precise would require lifting Merrill & Sabharwal’s characterization from decision problems to logspace transductions, which, to our knowledge, has not been established formally. We see our construction as complementary: Merrill & Sabharwal's construction uses polynomial padding by definition. Moreover, the logspace algorithm of Elberfeld et al. stores descriptors with O(k)O(k) vertices and enumerates candidate separators of size k+1k+1 by brute force (Lemma 3.13) so the space requirements of their algorithm grow with klog⁡nk \log n. A direct simulation would thus suggest polynomial padding whose degree grows with kk. Our construction uses only linear padding, FPT running time, and gives explicit bounds on the size of the transformer. We have added a discussion of this alternative to the revised paper and clarified that our contribution is an explicit construction with concrete space and time bounds.

Parallel algorithms. We agree that simulating a parallel algorithm, e.g., Bodlaender & Hagerup (1998), may yield a shallower construction. We do not claim our construction is depth-optimal. We chose Bodlaender’s linear-time algorithm because it allows us to give explicit size bounds with linear padding and FPT inference time. Precisely quantifying the resource requirements for a parallel simulation is an interesting direction for future work, which we have now added to the revised paper.

We thank the reviewer for these insightful comments, which substantially improved how we position our contribution!

There seems to be a typo in the MSO_1 formula for 3-colorability negation missing to the right of implies (since we want edges connecting different colored notes). Also adding parenthesis to the logical formulas on the middle of page 4 would definitely help with readability!

Thanks for pointing this out, we fixed the formula and added parentheses for better readability.

Table 1 reports automaton sizes parameterized by cliquewidth, whereas the main construction is parameterized by treewidth. Please clarify these differences and explain how these cliquewidth examples inform the resource requirements of the main treewidth construction.

Table 1 is parameterized by cliquewidth because hand-crafted automata are available in the literature for this setting. As every graph of treewidth kk has cliquewidth at most O(2k)O(2^{k}), the automata also apply to bounded-treewidth graphs, though only for MSO$_1$. Conversely, bounded cliquewidth also covers graph classes of unbounded treewidth, such as complete graphs. Unlike for treewidth, computing optimal term expressions is NP-hard in general, which is why our cliquewidth result assumes a term expression as input. Table 1 is thus meant to illustrate that the automata for many natural graph properties, and hence the parameter ss in our size bounds, can be much smaller than the worst-case bounds suggest. We have clarified this in the revised paper and added the transformer size bounds for bounded cliquewidth graphs to Corollary 5.1.

Michael Elberfeld, Andreas Jakoby, Till Tantau. Logspace Versions of the Theorems of Bodlaender and Courcelle. ECCC 2010.

William Merrill and Ashish Sabharwal. Exact expressive power of transformers with padding. NeurIPS 2025.

Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM Journal on Computing 1998.

Reviewer_GsSiOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the expressivity of transformers that operate over bounded treewidth graphs. The authors prove that every monadic second order (MSO) definable property over such graphs can be decided by log-precision average-hard attention transformers (AHAT). This extends prior work on transformer expressivity, notably on MSO properties over words (rather than graphs), which are equivalent to regular languages. A key contribution of the work is an O(n^3 log n) time (though see question below about "time") transformer that can compute a tree decomposition of a graph, as long as it is bounded by some fixed bound kk. The results presented for bounded treewidth graphs also have an analog in bounded cliquewidth graphs, which is valuable.

The authors have placed their work well in existing, and fast growing, literature on the topic of architecture expressivity. They also provide a concrete size bound for their transformer constructions, which is valuable.

Critical strengths

The main result of the paper, that log-precision AHAT transformers can recognize any MSO definable property of bounded treewidth (or bounded cliquewidth) graphs is a nice, general contribution. In contrast to constructions for some specific problems in many prior papers, it allows one to derive many interesting corollaries about a number of interesting properties, by leveraging extensive prior literature on MSO logic. The authors themselves use it to highlight several problems, including graphs connectivity, k-colorability, and planarity testing.

I am aware of relatively little literature on graph transformers, compared to transformers operating in token sequences. I think this paper is carefully written and will add quite some value to this subarea of architecture expressivity.

I like the authors' AI use statement: it's clear, meaningful, and very forthcoming in both crediting AI use (e.g., even for writing the AI use statement!) and taking direct responsibility for the content.

Critical weaknesses

I don't see any major weaknesses, only a few hopefully helpful suggestions. I should note that I have checked claims for plausibility and likelihood of correctness, but not validated detailed proofs which are all in the appendix.

Although it might be obvious to the authors, it would be best to clearly state, early on, what exactly a graph transformer is! The authors can simply restate the current lines 148-149 early on in the introduction, that graph transformers are simply regular transformers whose input is some linearized representation of graphs.

It's not immediately clear what the authors mean by "time" for a transformer, e.g., O(n3log⁡n)O(n^3 \log n) time references often. Does this represent the number of layers / loops? The actual sequential runtime during inference? Parallel runtime? Part (iii) in the proof of Thm 4.3 mentions simulating a DFA in FPT O(nlog⁡n)O(n \log n) time, which might mean parallel time, assuming each attention head computation (done in parallel at all token positions) takes time nn and this is repeated log⁡n\log n time across the architecture depth. But I am not sure if this is the intended interpretation.

I don't understand why, in line 287, the authors say that Thm 4.3 is purely existential. It appears constructive, e.g., it explains how one might implement a tree decomposition, then construct an automaton, then simulate a run of it on the input. Isn't this constructive already? The authors just haven't analyzed the size of the resulting construction. If so, this doesn't mean Thm 4.3 is purely existential. (It's possibly that I am missing something here.)

I found your cliquewidth results interesting and complementary. You might want to highlight them more at the intro (and perhaps even the abstract) level.

Similarly, some of the discussion currently at the end of section 5 (relation to known results about MSO-definable problems being solvable in AC0,TC0AC^0, TC^0 etc., a O(log⁡n)O(\log n) looping transformer construction (with padding) for all of TC1TC^1, MSO-expressibility over words, etc.) would be very helpful to state earlier, ideally right after the introduction. This will help the reader dispell some concerns and place the work accurately in the context of prior results.

Questions for authors
  • As noted above, could you please clarify what you mean precisely by the "time" taken by a transformer?

  • While I see that some prior decision-class inclusions along do not give an explicit transformer construction, could you clarify this specifically for the claim of computing a tree decomposition? Specifically, is the construction of Bodlaender (1993) that you simulate in the proof of Thm 4.4 know to be in TC1TC^1? If so, and assuming that inclusion is constructive, can't one combine that result with the result of Merrill et al (that log-looped padded transformers can simulate TC1TC^1), which is also constructive, to obtain a concrete construction for tree decomposition? It's possible that the size of such a construction may not be immediately obvious, and that would be a fair point to discuss in favor of a direct construction in Thm 4.4.

2 comments

We thank the reviewer for their detailed comments and the encouraging feedback!

We address each of the suggestions and questions below.

Although it might be obvious to the authors, it would be best to clearly state, early on, what exactly a graph transformer is! The authors can simply restate the current lines 148-149 early on in the introduction, that graph transformers are simply regular transformers whose input is some linearized representation of graphs.

We added this explanation to the introduction in lines 35-36.

It's not immediately clear what the authors mean by "time" for a transformer, e.g., O(n log^3n) time references often. Does this represent the number of layers / loops? The actual sequential runtime during inference? Parallel runtime? Part (iii) in the proof of Thm 4.3 mentions simulating a DFA in FPT O(n log n) time, which might mean parallel time, assuming each attention head computation (done in parallel at all token positions) takes time n and this is repeated log n time across the architecture depth. But I am not sure if this is the intended interpretation.

Thank you for pointing out this ambiguity! By “time” we refer to the total computational cost of a forward pass, i.e., the cost per layer (or iteration in case of a looped transformer), summed over all layers/iterations. For one layer operating on nn tokens and embedding dimension dd, we count the cost of attention, which is O(dn2)O(dn^2) for dense attention and O(dn)O(dn) when restricted by our structural masks, as well as the cost of the per-token MLPs. When making the cost model explicit, we noticed that our original bound did not account for the O(log⁡n)O(\log n) embedding dimension of the tree decomposition construction. We included it now in the revised version, yielding an FPT time bound of O(n3log⁡2n)O(n^3 \log^2 n); we have corrected this throughout the paper. This does not affect our main conclusions, as the FPT inference time remains near-cubic.

I don't understand why, in line 287, the authors say that Thm 4.3 is purely existential. It appears constructive, e.g., it explains how one might implement a tree decomposition, then construct an automaton, then simulate a run of it on the input. Isn't this constructive already? The authors just haven't analyzed the size of the resulting construction. If so, this doesn't mean Thm 4.3 is purely existential. (It's possibly that I am missing something here.)

This is a great point, thanks for bringing it up. We stated that the result is purely existential to make clear that we do not provide any guarantees on actually being able to learn such a transformer from data (although this would be very interesting for follow-up work!). However, one of the main strengths of our contribution is that we actually provide concrete constructions, from which we then derive architecture complexity bounds (Theorem 4.5 and Corollary 5.1).

I found your cliquewidth results interesting and complementary. You might want to highlight them more at the intro (and perhaps even the abstract) level.

We now mention the results earlier in the revised paper.

Similarly, some of the discussion currently at the end of section 5 (relation to known results about MSO-definable problems being solvable in AC0, TC0, etc., a O(log n) looping transformer construction (with padding) for all of TC1, MSO-expressibility over words, etc.) would be very helpful to state earlier, ideally right after the introduction. This will help the reader dispell some concerns and place the work accurately in the context of prior results.

We moved part of the discussion to the related work.

We thank the reviewer again for their interest in our work and for their help in improving our paper!

As noted above, could you please clarify what you mean precisely by the "time" taken by a transformer?

Please refer to our answer to your comment above.

While I see that some prior decision-class inclusions along do not give an explicit transformer construction, could you clarify this specifically for the claim of computing a tree decomposition? Specifically, is the construction of Bodlaender (1993) that you simulate in the proof of Thm 4.4 know to be in TC1? If so, and assuming that inclusion is constructive, can't one combine that result with the result of Merrill et al (that log-looped padded transformers can simulate TC1), which is also constructive, to obtain a concrete construction for tree decomposition? It's possible that the size of such a construction may not be immediately obvious, and that would be a fair point to discuss in favor of a direct construction in Thm 4.4.

Thank you for this insightful question! The specific algorithm by Bodlaender (1993) is sequential, so its direct simulation does not give a log-depth construction. However, as reviewer nsnL pointed out as well, the problem of computing bounded-width tree decompositions is in logspace (Elberfeld et al., 2010), and hence in TC$^1$. Combined with Merrill & Sabharwal (2025), and assuming the extension from decision problems to logspace transductions, this suggests the existence of log-looped padded transformers that compute tree decompositions. We chose Bodlaender’s algorithm deliberately because of its FPT linear running time, which allows us to give explicit resource bounds with linear padding and FPT inference time. In contrast, the discussed logspace alternative suggests polynomial padding whose degree may depend on kk. We had not considered this route before, and we have added a discussion of it to the revised paper.

Hans L Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. STOC 1993.

Michael Elberfeld, Andreas Jakoby, Till Tantau. Logspace Versions of the Theorems of Bodlaender and Courcelle. ECCC 2010.

William Merrill and Ashish Sabharwal. Exact expressive power of transformers with padding. NeurIPS 2025.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.