Dynamic Membership for Regular Tree Languages

Antoine Amarilli; Charles Paperman; Corentin Barloy; Louis Jachiet

REVIEW 1 major objections 6 minor 29 references

Dynamic Membership for Regular Tree Languages

T0 review · 1 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read For any fixed regular forest language, membership can be maintained in $O(\log n/\log\log n)$ per relabeling update, matching the known lower bound; with a neutral letter, constant-time updatability is conditionally exactly the…

desk verdict Solid upper bound and a nice conditional dichotomy, but the proof of the algebraic characterization has a real gap in Fact E.10 that needs fixing. read the letter →

arxiv 2504.17536 v2 pith:BW5ZP4FP submitted 2025-04-24 cs.FL cs.DS

Antoine Amarilli , Corentin Barloy , Louis Jachiet , Charles Paperman This is my paper · ORCID

classification cs.FLcs.DS MSC 68Q4568P0520M35

keywords regulartreelanguagesdynamicmembershiprelabelingupdatesforestalgebrasalmost-commutativeincrementalschemavalidationcontractionprefix-U1

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

The paper studies dynamic membership: fix a regular language of forests, and after each node relabeling decide whether the current forest is still in the language. It proves a general upper bound of $O(\log n/\log\log n)$ per update for every regular forest language, closing the previous $O(\log n)$ gap and matching known lower bounds. It then isolates the almost-commutative forest languages—finite Boolean combinations of regular commutative languages (membership depends only on letter counts) and virtually-singleton languages (membership fixes a small projection)—and shows these can be maintained in constant time per update. For languages with a neutral letter, one that can be deleted without changing membership, the paper proves a conditional dichotomy: under the prefix-U1 conjecture, constant-time updatability holds exactly for almost-commutative languages. This matters because it turns incremental schema validation for XML-like trees from a collection of heuristics into a classification with a decidable algebraic criterion.

What carries the argument

The load-bearing objects are forest algebras, LCRS-connected clustering, and the ZG equation. A forest algebra is a pair of finite monoids, vertical and horizontal, that compose tree contexts and forests, giving a finite algebraic summary of a regular forest language; the algorithm tabulates evaluations of small clusters in this algebra. The clustering scheme partitions the tree into $O(\log n)$-sized LCRS-connected pieces, meaning connected along first-child and next-sibling edges, evaluates each cluster by tabulation, and recurses on the induced forest of clusters, shrinking the size by a factor $\Theta(\log n)$ at each level. The classification rests on the ZG equation $x^{\omega+1} y = y x^{\omega+1}$ on the vertical monoid, which forces all group elements to be central and exactly characterizes the almost-commutative languages.

What would settle it

Build a worst-case $O(1)$-per-operation data structure for prefix-U1 in the RAM model with unit cost and logarithmic word size; this would refute Conjecture 6.1 and break the conditional lower bound. Equally decisive would be a regular forest language with a neutral letter that is not almost-commutative but provably has $O(1)$ dynamic membership under relabelings.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claims are Theorem 4.1 and Theorem 6.2. Theorem 4.1 says any fixed regular forest language admits a dynamic membership algorithm running in $O(\log n/\log\log n)$ after linear-time preprocessing, where $n$ is the number of nodes, matching the $\Omega(\log n/\log\log n)$ cell-probe lower bound inherited from marked-ancestor and word-language problems. Theorem 6.2 says that, assuming Conjecture 6.1, a regular forest language with a neutral letter has constant-time dynamic membership exactly when the language is almost-commutative; the algebraic content of 'almost-commutative' is that the vertical monoid of the syntactic forest algebra satisfies the ZG equation $x^{\omega+1} y = y x^{\omega+1}$. The paper also proves the characterization is decidable from a tree automaton, and that without a neutral letter the characterization fails, since the language 'a node labeled $a$ whose next sibling is labeled $b$' is maintainable in constant time but is not almost-commutative.

Load-bearing premise

The conditional half of the classification stands on Conjecture 6.1, which says the prefix-U1 problem—maintaining a growing and shrinking set of marked positions while answering whether a given prefix contains a mark—has no constant-time-per-operation data structure in the RAM model; if that conjecture is false, the lower-bound half of Theorem 6.2 collapses.

Editorial extensions

If this is right

Every regular forest language, not just selected ones, can now be maintained at the $O(\log n/\log\log n)$ speed limit under relabeling updates, with linear-time preprocessing.
The constant-time class is understood algebraically: being a finite Boolean combination of regular-commutative and virtually-singleton languages is decidable from a tree automaton.
Under the prefix-U1 conjecture, any language with a neutral letter that updates in constant time must be almost-commutative, so schema designers can check in advance whether a schema can be maintained in $O(1)$ per relabeling.
The $O(1)$ upper bound for almost-commutative languages extends the word-language constant-time classification to ordered forests, the setting relevant to XML-style incremental validation.
The lower-bound side imports the existential marked-ancestor hardness, so the general algorithm is optimal in the cell-probe model even for very simple regular forest languages.

Reading between the lines

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

A natural next step, not claimed in the paper, is to test whether the ZG criterion also governs $O(1)$ maintainability without a neutral letter; the paper's own example shows the boundary must be wider there.
Although the paper focuses on relabelings, the recursive clustering machinery seems transplantable to shape-changing updates like leaf insertions and deletions; verifying that would require new arguments, not just new theorems.
For practitioners, the dichotomy implies a schema triage rule: check almost-commutativity first and use the $O(1)$ data structure when it holds, otherwise fall back to the general logarithmic algorithm.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Two things to know. First, the O(log n / log log n) dynamic membership algorithm for arbitrary regular tree languages looks correct and closes a real gap. The clustering and tabulation approach is well explained, and the recursion depth analysis checks out. Second, the conditional dichotomy for constant-time maintainability under a neutral letter is the right kind of result to have, but the proof of its main algebraic ingredient, Theorem 6.4, is not complete as written.

The problem is Fact E.10 in Appendix E.1.3. It claims every forest with more than |V|^{5|V|}6^{|V|} nodes has an idempotent factor. The proof splits into wide, deep, and balanced cases. The balanced case says a forest with branching < |V|^{5|V|} and depth < |V|^{5|V|} has size less than the product of those bounds. That is false: a complete B-ary tree of depth D has size roughly B^D, not B·D. For |V| ≥ 2 this is much larger than the stated threshold, so the case analysis misses exponentially large balanced forests. Since Fact E.10 feeds directly into Lemma E.12, which underlies the backward direction of Theorem 6.4, the characterization is not established. The gap looks fixable—take the threshold to be something like B^D or use Ramsey-style arguments—but as it stands the proof has a hole.

The reader's report did not catch this; it flagged only a minor typo. I think the rest of the structural material is in good shape. The upper bound is self-contained, and the lower bound reductions are honestly presented as conditional on Conjecture 6.1. The paper also clearly states that the characterization needs the neutral-letter assumption and gives a counterexample without it. That is good practice.

Who gets value from this: anyone working on dynamic algorithms for tree automata or on algebraic varieties of regular languages. The upper bound alone is worth having. The dichotomy is attractive and probably true, but I would not cite the characterization until the proof is patched. I would bring the paper to a reading group; the gap is educational.

My recommendation to the editor: send it to peer review. A serious referee should engage with it, but the acceptance should hinge on the authors repairing Fact E.10 and verifying that Lemma E.12 goes through with a corrected bound. This is a fixable flaw in an otherwise strong paper, not a fatal one.

Referee Report

1 major / 6 minor

Summary. The paper studies dynamic membership for regular forest languages under node relabelings: fix a regular forest language L and a forest T, and maintain whether T belongs to L while single node labels are changed. The first contribution (Theorem 4.1) is an O(log n / log log n) per-update algorithm for every fixed regular forest language, matching known lower bounds; the algorithm recursively clusters the forest into O(log n)-size clusters, evaluates clusters by tabulation, and reduces to a forest of clusters. The second contribution introduces almost-commutative forest languages, defined as finite Boolean combinations of regular-commutative and virtually-singleton languages, and proves (Theorem 5.5) that they admit O(1) dynamic membership. The third contribution (Theorem 6.2) is a conditional converse: assuming the prefix-U1 conjecture of [3], a regular forest language with a neutral letter has O(1) dynamic membership iff it is almost-commutative. The proof rests on an algebraic characterization (Theorem 6.4): almost-commutative languages are exactly those whose syntactic forest algebra satisfies the ZG equation on its vertical monoid. Detailed proofs are deferred to the appendices, and the lower bound is explicitly conditional on Conjecture 6.1.

Significance. If the proof gap noted below is repaired, the paper makes a solid contribution. It closes the known gap between O(log n) and O(log n / log log n) for dynamic membership in arbitrary regular tree languages; it identifies a natural and decidable class of languages with constant-time maintenance; and it gives a clean conditional algebraic dichotomy under the same hypothesis used in the word case. The paper is careful to state Conjecture 6.1 explicitly, to show that the neutral-letter assumption is necessary (Example 6.6), and to provide detailed appendices for the main technical claims. The appendices contain many self-contained proofs and the reduction arguments are clearly laid out. The main weakness is a genuine size-bound error in the proof of Fact E.10 in Appendix E.1.3, which leaves the hard direction of Theorem 6.4 incomplete as written; the error appears localized and repairable, so the overall approach remains credible.

major comments (1)

[Appendix E.1.3, Fact E.10] The proof of the third case is incorrect. With B = D = |V|^{5|V|}, the maximum number of nodes of a forest in which every node has fewer than B children and every root-to-leaf path has length less than D is at least B^D, not less than B·D. For instance, when |V|=2 we have B=1024, D=1024 and N = |V|^{5|V|}6^{|V|} = 36864; a complete binary tree of depth 1023 has 2^{1024}-1 nodes, which is far larger than N, yet falls into the third case. Thus the stated threshold does not exclude the third case, and Fact E.10 is not proved as written. Since Lemma E.12 invokes Fact E.10 on forests whose size is only known to exceed N, the extraction argument, and with it the hard direction of Theorem 6.4, is incomplete. The gap appears repairable by taking N to be a sufficiently large exponential bound such as B^D+1; the remainder of the proof uses only that N is a fixed constant, so such a change is compatible with the rest of the argument.

minor comments (6)

[Appendix C.4, Proposition 4.10] The proof derives the complexity bound using a value k+1 = ceil(log n / (8|Σ|)), although the proposition is stated for arbitrary k and no n is mentioned; please replace this with the direct bound O((4|Σ|)^{k+1}) and explain how the constant c_{V,H} is chosen so that k = floor(log n / c_{V,H}) makes the preprocessing linear.
[Proposition 4.10 statement] The statement says that internal nodes have labels in H, but a (V,H)-forest labels internal nodes by elements of V and leaves by elements of H; the appendix uses the correct convention, so the proposition statement contains a typo.
[Fact E.10 proof, wide case] In the first case the proof invokes Lemma E.11 'on the horizontal monoid', but the contexts C_i evaluate to elements of the vertical monoid V; this should be 'on the vertical monoid'.
[Lemma E.7 proof] In the chain following Lemma E.7, the text writes 'because h = w⊕ϵ'; since w = h⊕□, the correct identity is h = w⊙ϵ.
[Theorem 6.4, final proof] The residues are taken modulo m, the idempotent power of V, but several occurrences use 'n' instead of 'm', for example 'r ∈ {0,...,n−1}^{Σ+}' and 'x_a ≡ r_a modulo n'.
[Section 4] The symbol c_{V,H} is used both for the tabulation constant in Proposition 4.10 and for the constant in Claim 4.8; using distinct names would avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the upper bounds and the algebraic characterization are proved from independent constructions, and the conditional lower bound transparently relies on a stated conjecture from prior work rather than assuming the target result.

full rationale

The derivation chain is not circular. Theorem 4.1 is proved directly by clustering and tabulation (Claims 4.6, 4.8, 4.9, Proposition 4.10), with no fitted parameters and no appeal to the theorem being proved. Theorem 5.5 follows from data structures for commutative and virtually-singleton languages, built from elementary Parikh-image and doubly-linked-list arguments; the citations to [3] and [26] are for word-case techniques, not for the forest result. Theorem 6.4 is the substantive algebraic characterization: almost-commutative is defined syntactically as a Boolean combination, while ZG is defined by a monoid equation, and the two are connected by an original normal-form proof (Lemmas E.9 and E.12) rather than by stipulation. The conditional lower bound (Theorem 6.2 and Proposition 6.5) reduces tree languages with a neutral letter to a word-language lower bound from the authors' prior work [3], subject to Conjecture 6.1; this is a transparent conditional statement, and the conjecture itself is explicitly left open, so the reduction is not a derivation of the target from itself. I therefore find no circular step. Separately flagged as a non-circular correctness concern: in Appendix E.1.3, Fact E.10's third case bounds a forest with branching factor <B and depth <D by B·D, but a balanced tree can have exponentially many nodes (about B^D), and the theorem's threshold |V|^{5|V|}6^{|V|} is smaller than B·D = |V|^{10|V|}; the proof as written does not cover all forests above the stated threshold. This is a gap in the written proof of the ZG characterization, not a circularity.

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

The central claims rely on standard automata theory, the prefix-U1 conjecture, and the neutral-letter restriction. No new physical entities or fitted parameters are introduced. Constants such as k, m, and N are explicit bounds chosen from the algebra and input size, not fitted to data.

assumptions (4)

ad hoc to paper The prefix-U1 problem has no O(1)-time algorithm in the RAM model with unit cost and logarithmic word size (Conjecture 6.1).
Used for the conditional lower bound in Proposition 6.5 and Theorem 6.2 from [3]. If false, the dichotomy may fail. The paper states this as a conjecture, not a theorem.
domain assumption The language has a neutral letter, that is, a letter that can be removed without changing membership.
Restricts Theorem 6.2; Example 6.6 shows the characterization is false without this assumption.
standard math Standard RAM model with unit cost and logarithmic word size.
Used for all complexity statements, including lower bounds inherited from marked ancestor and word dynamic membership results.
standard math Regular forest languages are exactly those recognized by finite forest algebras, and the syntactic forest algebra exists and is minimal.
Imported from [9] and used in Lemma 3.1 and throughout Section 6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Dynamic Membership for Regular Tree Languages." pith.science (2026). https://pith.science/paper/BW5ZP4FP

@misc{pith2026250417536,
  author       = {Pith},
  title        = {Pith review of: Dynamic Membership for Regular Tree Languages},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BW5ZP4FP}},
  note         = {Machine review of arXiv:2504.17536}
}

abstract

We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet $\Sigma$ and a regular tree language $L$ over $\Sigma$ (expressed, e.g., as a tree automaton), we are given a tree $T$ with labels in $\Sigma$, and we must maintain the information of whether the tree $T$ belongs to $L$ while handling relabeling updates that change the labels of individual nodes in $T$. Our first contribution is to show that this problem admits an $O(\log n / \log \log n)$ algorithm for any fixed regular tree language, improving over known $O(\log n)$ algorithms. This generalizes the known $O(\log n / \log \log n)$ upper bound over words, and it matches the lower bound of $\Omega(\log n / \log \log n)$ from dynamic membership to some word languages and from the existential marked ancestor problem. Our second contribution is to introduce a class of regular languages, dubbed almost-commutative tree languages, and show that dynamic membership to such languages under relabeling updates can be decided in constant time per update. Almost-commutative languages generalize both commutative languages and finite languages: they are the analogue for trees of the ZG languages enjoying constant-time dynamic membership over words. Our main technical contribution is to show that this class is conditionally optimal when we assume that the alphabet features a neutral letter, i.e., a letter that has no effect on membership to the language. More precisely, we show that any regular tree language with a neutral letter which is not almost-commutative cannot be maintained in constant time under the assumption that the prefix-U1 problem from (Amarilli, Jachiet, Paperman, ICALP'21) also does not admit a constant-time algorithm.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 26 canonical work pages

[3]

Dynamic Membership for Regular Languages

Antoine Amarilli, Louis Jachiet, and Charles Paperman. https://arxiv.org/abs/2102.07728 Dynamic membership for regular languages . In ICALP https://easyconferences.eu/icalp2021/ , 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.116 doi:10.4230/LIPIcs.ICALP.2021.116

work page Pith review arXiv 2021
[1]

Marked ancestor problems http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3834&rep=rep1&type=pdf

Stephen Alstrup, Thore Husfeldt, and Theis Rauhe. Marked ancestor problems http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3834&rep=rep1&type=pdf. In FOCS , 1998

work page 1998
[2]

Enumeration on Trees under Relabelings

Antoine Amarilli, Pierre Bourhis, and Stefan Mengel. https://arxiv.org/abs/1709.06185 Enumeration on trees under relabelings . In ICDT https://edbticdt2018.at/ , 2018. https://doi.org/10.4230/LIPIcs.ICDT.2018.5 doi:10.4230/LIPIcs.ICDT.2018.5

work page Pith review arXiv 2018
[4]

Locality and Centrality: The Variety ZG

Antoine Amarilli and Charles Paperman. https://arxiv.org/abs/2102.07724 Locality and centrality: The variety ZG . LMCS https://lmcs.episciences.org/ , 2023. https://doi.org/10.46298/LMCS-19(4:4)2023 doi:10.46298/LMCS-19(4:4)2023

work page Pith review arXiv 2023
[5]

http://db.ucsd.edu/wp-content/uploads/pdfs/212.pdf Incremental validation of XML documents

Andrey Balmin, Yannis Papakonstantinou, and Victor Vianu. http://db.ucsd.edu/wp-content/uploads/pdfs/212.pdf Incremental validation of XML documents . TODS , 29(4), 2004

work page 2004
[6]

On the complexity of regular languages

Corentin Barloy. On the complexity of regular languages . PhD thesis, Université de Lille, 2024. https://theses.hal.science/tel-04820899v1/

work page 2024
[7]

First-order expressibility of languages with neutral letters or: The C rane B each conjecture

David A Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, and Denis Th \'e rien. First-order expressibility of languages with neutral letters or: The C rane B each conjecture. JCSS , 70(2), 2005. https://doi.org/10.1016/j.jcss.2004.07.004 doi:10.1016/j.jcss.2004.07.004

work page doi:10.1016/j.jcss.2004.07.004 2005
[8]

Parallel algorithms with optimal speedup for bounded treewidth

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

work page 1998

Show all 29 references

[9]

Forest algebras

Mikolaj Bojanczyk and Igor Walukiewicz. Forest algebras. Automata and logic: history and perspectives , 2008

2008
[10]

Recognisable languages over monads, 2015

Mikołaj Bojańczyk. Recognisable languages over monads, 2015. https://arxiv.org/abs/1502.04898 arXiv:1502.04898

2015 arXiv
[11]

Tree automata: T echniques and applications, 2008

Hubert Comon, Max Dauchet, R \'e mi Gilleron, Florent Jacquemard, Denis Lugiez, Christof L \"o ding, Sophie Tison, and Marc Tommasi. Tree automata: T echniques and applications, 2008. https://hal.science/hal-03367725

2008
[12]

Automata, Languages and Machines, Vol

Samuel Eilenberg. Automata, Languages and Machines, Vol. B . Academic Press, 1976

1976
[13]

Dynamic algorithms for the Dyck languages https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.4615&rep=rep1&type=pdf

Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and S ren Skyum. Dynamic algorithms for the Dyck languages https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.4615&rep=rep1&type=pdf. In WADS , 1995
[14]

The cell probe complexity of dynamic data structures https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.453.9085&rep=rep1&type=pdf

Michael Fredman and Michael Saks. The cell probe complexity of dynamic data structures https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.453.9085&rep=rep1&type=pdf. In STOC , 1989

1989
[15]

Optimal tree contraction in the EREW model

Hillel Gazit, Gary L Miller, and Shang-Hua Teng. Optimal tree contraction in the EREW model. In Concurrent Computations: Algorithms, Architecture, and Technology . Springer, 1988

1988
[16]

The dynamic complexity of formal languages https://arxiv.org/abs/0812.1915

Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages https://arxiv.org/abs/0812.1915. TOCL , 13(3), 2012

1915 arXiv
[17]

Fast algorithms for finding nearest common ancestors

Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing , 13(2), 1984

1984
[18]

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.6315&rep=rep1&type=pdf Hardness results for dynamic problems by extensions of F redman and S aks' chronogram method

Thore Husfeldt and Theis Rauhe. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.6315&rep=rep1&type=pdf Hardness results for dynamic problems by extensions of F redman and S aks' chronogram method . In ICALP , 1998
[19]

A Ramsey theorem for finite monoids

Isma\" e l Jecker. A Ramsey theorem for finite monoids . In STACS , volume 187, 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.44 doi:10.4230/LIPIcs.STACS.2021.44

2021 doi
[20]

Bounded-depth circuits: S eparating wires from gates

Michal Kouck \`y , Pavel Pudl \'a k, and Denis Th \'e rien. Bounded-depth circuits: S eparating wires from gates. In STOC , 2005. https://doi.org/10.1145/1060590.1060629 doi:10.1145/1060590.1060629

2005
[21]

Katja Losemann and Wim Martens. https://www.theoinf.uni-bayreuth.de/pool/documents/Paper2011-15/Paper2014/MSO_Queries_on_Trees_Enumerating_Answers_under_Updates_preprint.pdf MSO queries on trees: E numerating answers under updates . In CSL--LICS , 2014. https://doi.org/10.1145...

2014
[22]

Parallel tree contraction and its application

Gary L Miller and John H Reif. Parallel tree contraction and its application. In FOCS , 1985

1985
[23]

Mathematical foundations of automata theory, 2014

Jean-Eric Pin. Mathematical foundations of automata theory, 2014. URL: http://www.irif.fr/ jep/PDF/MPRI/MPRI.pdf

2014
[24]

Mathematical foundations of automata theory

Jean-\'Eric Pin. Mathematical foundations of automata theory. https://www.irif.fr/ jep/PDF/MPRI/MPRI.pdf, 2019

2019
[25]

Jonas Schmidt, Thomas Schwentick, and Jennifer Todtenhoefer. On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.81. In MFCS , volume 272, 2023. URL:...

doi
[26]

Dynamic word problems http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.868.4450&rep=rep1&type=pdf

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.868.4450&rep=rep1&type=pdf. JACM , 44(2), 1997

1997
[27]

The variety generated by finite nilpotent monoids

Howard Straubing. The variety generated by finite nilpotent monoids. Semigroup Forum , 24(1), 1982. https://doi.org/10.1007/bf02572753 doi:10.1007/bf02572753

1982 doi
[28]

Dynamic complexity of regular languages: Big changes, small work

Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Dynamic complexity of regular languages: Big changes, small work. In CSL , 2023

2023
[29]

The complexity of relational query languages

Moshe Y Vardi. The complexity of relational query languages. In STOC , 1982

1982

Pith tools

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

[1] [3]

Dynamic Membership for Regular Languages

Antoine Amarilli, Louis Jachiet, and Charles Paperman. https://arxiv.org/abs/2102.07728 Dynamic membership for regular languages . In ICALP https://easyconferences.eu/icalp2021/ , 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.116 doi:10.4230/LIPIcs.ICALP.2021.116

work page Pith review arXiv 2021

[2] [1]

Marked ancestor problems http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3834&rep=rep1&type=pdf

Stephen Alstrup, Thore Husfeldt, and Theis Rauhe. Marked ancestor problems http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3834&rep=rep1&type=pdf. In FOCS , 1998

work page 1998

[3] [2]

Enumeration on Trees under Relabelings

Antoine Amarilli, Pierre Bourhis, and Stefan Mengel. https://arxiv.org/abs/1709.06185 Enumeration on trees under relabelings . In ICDT https://edbticdt2018.at/ , 2018. https://doi.org/10.4230/LIPIcs.ICDT.2018.5 doi:10.4230/LIPIcs.ICDT.2018.5

work page Pith review arXiv 2018

[4] [4]

Locality and Centrality: The Variety ZG

Antoine Amarilli and Charles Paperman. https://arxiv.org/abs/2102.07724 Locality and centrality: The variety ZG . LMCS https://lmcs.episciences.org/ , 2023. https://doi.org/10.46298/LMCS-19(4:4)2023 doi:10.46298/LMCS-19(4:4)2023

work page Pith review arXiv 2023

[5] [5]

http://db.ucsd.edu/wp-content/uploads/pdfs/212.pdf Incremental validation of XML documents

Andrey Balmin, Yannis Papakonstantinou, and Victor Vianu. http://db.ucsd.edu/wp-content/uploads/pdfs/212.pdf Incremental validation of XML documents . TODS , 29(4), 2004

work page 2004

[6] [6]

On the complexity of regular languages

Corentin Barloy. On the complexity of regular languages . PhD thesis, Université de Lille, 2024. https://theses.hal.science/tel-04820899v1/

work page 2024

[7] [7]

First-order expressibility of languages with neutral letters or: The C rane B each conjecture

David A Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, and Denis Th \'e rien. First-order expressibility of languages with neutral letters or: The C rane B each conjecture. JCSS , 70(2), 2005. https://doi.org/10.1016/j.jcss.2004.07.004 doi:10.1016/j.jcss.2004.07.004

work page doi:10.1016/j.jcss.2004.07.004 2005

[8] [8]

Parallel algorithms with optimal speedup for bounded treewidth

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

work page 1998