Dynamic membership for regular tree languages

DOI10.4230/LIPICS.MFCS.2025.8MaRDI QIDQ7310163zbMATH OpenFDO

Authors Antoine Amarilli, Corentin Barloy, Louis Jachiet, Charles Paperman

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.8

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Bounded-depth circuits
• Dynamic algorithms for the Dyck languages
• Dynamic complexity of regular languages: big changes, small work
• Dynamic membership for regular languages
• Dynamic word problems
• Enumeration on trees under relabelings
• Fast Algorithms for Finding Nearest Common Ancestors
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Locality and Centrality: The Variety ZG
• Marked ancestor problems
• MSO queries on trees: enumerating answers under updates
• On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• The dynamic complexity of formal languages
• The variety generated by finite nilpotent monoids

This page was built for publication: Dynamic membership for regular tree languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310163)