Imagen de Portada

A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Mengel, Stefan, Vinall-Smeeth, Harry
Formato:	Preprint
Publicado:	2024
Materias:	Databases Formal Languages and Automata Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Skyline Operators for Document Spanners
por: Amarilli, Antoine, et al.
Publicado: (2023)

Dynamic direct access of MSO query evaluation over strings
por: Bourhis, Pierre, et al.
Publicado: (2024)

The Complexity of Aggregates over Extractions by Regular Expressions
por: Doleschal, Johannes, et al.
Publicado: (2020)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
por: Kiefer, Stefan, et al.
Publicado: (2019)

Unambiguous Acceptance of Thin Coalgebras
por: Chernev, Anton, et al.
Publicado: (2025)

Forbidden-Context & Ordered Grammar Systems
por: Fernau, Henning, et al.
Publicado: (2026)

A framework for extraction and transformation of documents
por: Riveros, Cristian, et al.
Publicado: (2024)

A Unifying Perspective on Succinct Data Representations
por: Kimelfeld, Benny, et al.
Publicado: (2023)

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

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

MSO-Enumeration Over SLP-Compressed Unranked Forests
por: Lohrey, Markus, et al.
Publicado: (2024)

Designing and Comparing RPQ Semantics
por: Marsault, Victor, et al.
Publicado: (2026)

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

Bonding Grammars
por: Pshenitsyn, Tikhon
Publicado: (2024)

Detecting and Explaining (In-)equivalence of Context-Free Grammars
por: Schmellenkamp, Marko, et al.
Publicado: (2024)

Computational Model for Parsing Expression Grammars
por: Rubtsov, Alexander, et al.
Publicado: (2024)

On Decidability and Expressive Power of Fusion Grammars
por: Pshenitsyn, Tikhon
Publicado: (2023)

Tahr: The Generative Attribute Grammar Framework
por: Ciccaglione, Matteo, et al.
Publicado: (2025)

Closure Properties of General Grammars -- Formally Verified
por: Dvorak, Martin, et al.
Publicado: (2023)

Idefix-Closed Languages and Their Application in Contextual Grammars
por: Ködding, Marvin, et al.
Publicado: (2025)

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

Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
por: Bell, Jason P., et al.
Publicado: (2022)

Regular Grammars for Sets of Graphs of Tree-Width 2
por: Bozga, Marius, et al.
Publicado: (2024)

Characterizations of Controlled Generation of Right Linear Grammars with Unknown Behaviors
por: Ise, Daihei, et al.
Publicado: (2024)

Uniform Membership for Hyperedge Replacement Grammars and Related Decision Problems
por: Pshenitsyn, Tikhon
Publicado: (2025)

Verifying Parameterized Networks Specified by Vertex-Replacement Graph Grammars
por: Iosif, Radu, et al.
Publicado: (2025)

Complex event recognition meets hierarchical conjunctive queries
por: Pinto, Dante, et al.
Publicado: (2024)

Shuffles of Context-Free Languages along Regular Trajectories
por: Barloy, Corentin, et al.
Publicado: (2026)

Unraveling Syntax: How Language Models Learn Context-Free Grammars
por: Schulz, Laura Ying, et al.
Publicado: (2025)

Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners
por: Schmid, Markus L., et al.
Publicado: (2020)

Complex event recognition under time constraints: towards a formal framework for efficient query evaluation
por: García, Julián, et al.
Publicado: (2025)

Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition
por: Nogami, Taisei, et al.
Publicado: (2024)

Distributional Learning of Context-Free Languages under Fixed Finite-Monoid Typing
por: Kuriyama, Takayuki
Publicado: (2014)

Matching walks that are minimal with respect to edge inclusion
por: Marsault, Victor
Publicado: (2024)

A Uniform Framework for Problems on Context-Free Grammars
por: Esparza, Javier, et al.
Publicado: (2024)

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

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
por: Yamakami, Tomoyuki
Publicado: (2024)

Context-Free Languages of String Diagrams
por: Earnshaw, Matt, et al.
Publicado: (2024)

Extended Stone Duality via Monoidal Adjunctions
por: Lenke, Fabian, et al.
Publicado: (2024)

Constrained Decoding of Diffusion LLMs with Context-Free Grammars
por: Mündler, Niels, et al.
Publicado: (2025)