Cover Image

On Decidability and Expressive Power of Fusion Grammars

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Pshenitsyn, Tikhon
Format:	Preprint
Published:	2023
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

Bonding Grammars
by: Pshenitsyn, Tikhon
Published: (2024)

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

First-Order Intuitionistic Linear Logic and Hypergraph Languages
by: Pshenitsyn, Tikhon
Published: (2025)

On the Expressive Power of Regular Expressions with Backreferences
by: Nogami, Taisei, et al.
Published: (2023)

Deciding Subtyping for Asynchronous Multiparty Sessions
by: Li, Elaine, et al.
Published: (2024)

On Decidability Timed Automata with 2 Parametric Clocks
by: Bersani, Marcello M., et al.
Published: (2025)

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

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

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

Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable
by: Bizière, Clotilde, et al.
Published: (2024)

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

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

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

Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
by: Gallot, Paul, et al.
Published: (2023)

Deciding whether an Attributed Translation can be realized by a Top-Down Transducer
by: Maneth, Sebastian, et al.
Published: (2023)

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

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

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

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

Decidable problems in substitution shifts
by: Béal, Marie-Pierre, et al.
Published: (2021)

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
by: Roop, Partha, et al.
Published: (2026)

A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
by: Mengel, Stefan, et al.
Published: (2024)

V-Star: Learning Visibly Pushdown Grammars from Program Inputs
by: Jia, Xiaodong, et al.
Published: (2024)

New Insights into the Decidability of Opacity in Timed Automata
by: Deng, Weilin, et al.
Published: (2025)

Decidability and Characterization of Expansivity for Group Cellular Automata
by: Castronuovo, Niccolo', et al.
Published: (2025)

The Power-Set Construction for Tree Algebras
by: Blumensath, Achim
Published: (2022)

Backward Responsibility in Transition Systems Using General Power Indices
by: Baier, Christel, et al.
Published: (2024)

A Divide and Conquer Algorithm for Deciding Group Cellular Automata Dynamics
by: Castronuovo, Niccolo', et al.
Published: (2025)

Decidability Problems for Micro-Stipula
by: Delzanno, Giorgio, et al.
Published: (2025)

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

Exact Expressive Power of Transformers with Padding
by: Merrill, William, et al.
Published: (2025)

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

Deciding DFA-Primality is NP-Hard
by: Spenner, Daniel Alexander
Published: (2026)

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
by: Bozga, Marius, et al.
Published: (2026)

Tree-Verifiable Graph Grammars
by: Chimes, Mark, et al.
Published: (2024)

Determinization of Min-Plus Weighted Automata is Decidable
by: Almagor, Shaull, et al.
Published: (2025)

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

Characterization and Decidability of FC-Definable Regular Languages
by: Thompson, Sam M., et al.
Published: (2025)

Negated String Containment is Decidable (Technical Report)
by: Havlena, Vojtěch, et al.
Published: (2025)

A Language and Methodology based on Scenarios, Grammars and Views, for Administrative Business Processes Modelling
by: Ndadji, Milliam Maxime Zekeng, et al.
Published: (2020)