Cover Image

Bounded treewidth, multiple context-free grammars, and downward closures

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aiswarya, C., Baumann, Pascal, Saivasan, Prakash, Schütze, Lia, Zetzsche, Georg
Format:	Preprint
Published:	2025
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The complexity of downward closures of indexed languages
by: Mandel, Richard, et al.
Published: (2026)

Verifying Unboundedness via Amalgamation
by: Anand, Ashwani, et al.
Published: (2024)

Infinite-state Games with Energy Objectives Beyond Counters
by: Sağlam, Irmak, et al.
Published: (2026)

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
by: Bergsträßer, Pascal, et al.
Published: (2024)

Existential Definability over the Subword Ordering
by: Baumann, Pascal, et al.
Published: (2022)

Separability in Büchi Vass and Singly Non-Linear Systems of Inequalities
by: Baumann, Pascal, et al.
Published: (2024)

Slice closures of indexed languages and word equations with counting constraints
by: Ciobanu, Laura, et al.
Published: (2024)

The complexity of separability for semilinear sets and Parikh automata
by: Collins, Elias Rojas, et al.
Published: (2024)

Satisfiability of Context-free String Constraints with Subword-ordering and Transducers
by: Aiswarya, C, et al.
Published: (2024)

Directed Regular and Context-Free Languages
by: Ganardi, Moses, et al.
Published: (2024)

Separability and Non-Determinizability of WSTS
by: Czerwiński, Wojciech, et al.
Published: (2023)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
by: Zetzsche, Stefan, et al.
Published: (2024)

Equivalence of Deterministic Weighted Real-time One-Counter Automata
by: Mathew, Prince, et al.
Published: (2024)

Length Generalization Bounds for Transformers
by: Yang, Andy, et al.
Published: (2026)

Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
by: Lichtner, Kilian, et al.
Published: (2025)

A short survey around the pumping lemma for context-free languages
by: Gullà, Gabriele
Published: (2024)

Bounded Languages Described by GF(2)-grammars
by: Makarov, Vladislav
Published: (2019)

Automata for the commutative closure of regular sets
by: Becher, Verónica, et al.
Published: (2025)

All about unambiguous polynomial closure
by: Place, Thomas, et al.
Published: (2022)

Quantum finite automata and linear context-free languages: a decidable problem
by: Bertoni, A., et al.
Published: (2013)

Permutation closure for multiple context-free languages
by: Duncan, Andrew, et al.
Published: (2025)

$O_2$ is a multiple context-free grammar: an implementation-, formalisation-friendly proof
by: Caminati, Marco B.
Published: (2024)

Checking History-Determinism is NP-hard for Parity Automata
by: Prakash, Keya
Published: (2023)

The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
by: Lehtinen, Karoliina, et al.
Published: (2025)

General Decidability Results for Systems with Continuous Counters
by: Balasubramanian, A. R., et al.
Published: (2025)

The Counting Power of Transformers
by: Sälzer, Marco, et al.
Published: (2025)

Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata
by: Acharya, Rohan, et al.
Published: (2024)

History-Deterministic Büchi Automata are Succinct
by: Casares, Antonio, et al.
Published: (2026)

Deciding Conjugacy of a Rational Relation
by: Aiswarya, C., et al.
Published: (2023)

Optimal Approximate Minimization of One-Letter Weighted Finite Automata
by: Lacroce, Clara, et al.
Published: (2023)

Languages of Boundedly-Ambiguous Vector Addition Systems with States
by: Czerwiński, Wojciech, et al.
Published: (2025)

A Tree Sampler for Bounded Context-Free Languages
by: Considine, Breandan
Published: (2024)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
by: Shakiba, Yousef, et al.
Published: (2025)

Realisability and Complementability of Multiparty Session Types
by: Di Giusto, Cinzia, et al.
Published: (2025)

Inform: From Compartmental Models to Stochastic Bounded Counter Machines
by: Leys, Tim, et al.
Published: (2024)

A Complexity Bound for Determinisation of Min-Plus Weighted Automata
by: Almagor, Shaull, et al.
Published: (2026)

On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata
by: Casares, Antonio, et al.
Published: (2024)

Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
by: Wehar, Michael
Published: (2025)

Passive Model Learning of Visibly Deterministic Context-free Grammars
by: Muškardin, Edi, et al.
Published: (2025)

Congruence based proofs of the recognizability theorems for free many-sorted algebras
by: Vidal, Juan Climent, et al.
Published: (2018)