Buchumschlag

Characterization and Decidability of FC-Definable Regular Languages

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Thompson, Sam M., Schweikardt, Nicole, Freydenberger, Dominik D.
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Logic in Computer Science Formal Languages and Automata Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

FC-Datalog as a Framework for Efficient String Querying
von: Bell, Owen M., et al.
Veröffentlicht: (2025)

Algebraic Characterizations of Classes of Regular Languages in DynFO
von: Barloy, Corentin, et al.
Veröffentlicht: (2026)

Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
von: Czerwiński, Wojciech, et al.
Veröffentlicht: (2022)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
von: Barloy, Corentin, et al.
Veröffentlicht: (2025)

Decidability Problems for Micro-Stipula
von: Delzanno, Giorgio, et al.
Veröffentlicht: (2025)

Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs
von: Iosif, Radu, et al.
Veröffentlicht: (2023)

Determinization of Min-Plus Weighted Automata is Decidable
von: Almagor, Shaull, et al.
Veröffentlicht: (2025)

General Decidability Results for Systems with Continuous Counters
von: Balasubramanian, A. R., et al.
Veröffentlicht: (2025)

Negated String Containment is Decidable (Technical Report)
von: Havlena, Vojtěch, et al.
Veröffentlicht: (2025)

Deciding the synthesis problem for hybrid games through bisimulation
von: Dima, Catalin, et al.
Veröffentlicht: (2024)

Set Automata and Limits of Decidability of Two-Variable Logic on Data Words
von: Guha, Shibashis, et al.
Veröffentlicht: (2026)

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
von: Daviaud, Laure, et al.
Veröffentlicht: (2023)

Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
von: Mandrioli, Dino, et al.
Veröffentlicht: (2020)

Existential Definability over the Subword Ordering
von: Baumann, Pascal, et al.
Veröffentlicht: (2022)

Fractals from Regular Behaviours
von: Schmid, Todd, et al.
Veröffentlicht: (2023)

Effective MSO-Definability for Tree-width Bounded Models of an Inductive Separation Logic of Relations
von: Bueri, Lucas, et al.
Veröffentlicht: (2024)

A Completeness Theorem for Probabilistic Regular Expressions
von: Różowski, Wojciech, et al.
Veröffentlicht: (2023)

Synthesis of Computable Regular Functions of Infinite Words
von: Dave, V., et al.
Veröffentlicht: (2019)

On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle
von: Ancona, Davide, et al.
Veröffentlicht: (2025)

A Complete Propositional Dynamic Logic for Regular Expressions with Lookahead
von: Nakamura, Yoshiki
Veröffentlicht: (2026)

Characterizing the Polynomial-Time Minimizable $ω$-Automata
von: Radi, Bader Abu, et al.
Veröffentlicht: (2025)

HornStr: Invariant Synthesis for Regular Model Checking as Constrained Horn Clauses(Technical Report)
von: Jiang, Hongjian, et al.
Veröffentlicht: (2025)

Kofola 1.0: A Modular Approach to ω-Regular Complementation and Inclusion Checking (Technical Report)
von: Alexaj, Ondrej, et al.
Veröffentlicht: (2026)

Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity
von: Zhang, Yuanrui, et al.
Veröffentlicht: (2023)

A Myhill-Nerode Characterization and Active Learning for One-Clock Timed Automata
von: Doveri, Kyveli, et al.
Veröffentlicht: (2026)

PVASS Reachability is Decidable
von: Guttenberg, Roland, et al.
Veröffentlicht: (2025)

Logic and Languages of Higher-Dimensional Automata
von: Amrane, Amazigh, et al.
Veröffentlicht: (2024)

A Trichotomy for Regular Trail Queries
von: Martens, Wim, et al.
Veröffentlicht: (2019)

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
von: Czerwiński, Wojciech, et al.
Veröffentlicht: (2025)

A Uniform Framework for Language Inclusion Problems
von: Doveri, Kyveli, et al.
Veröffentlicht: (2024)

Random Graph Generation in Context-Free Graph Languages
von: Vastarini, Federico, et al.
Veröffentlicht: (2024)

RNN Generalization to Omega-Regular Languages
von: Pert, Charles, et al.
Veröffentlicht: (2025)

A Practical Specification Language for Automatic Quantum Program Verification (Technical Report)
von: Tsai, Wei-Lun, et al.
Veröffentlicht: (2026)

Automatic Generation of Safety-compliant Linear Temporal Logic via Large Language Model: A Self-supervised Framework
von: Li, Junle, et al.
Veröffentlicht: (2025)

Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries
von: Figueira, Diego, et al.
Veröffentlicht: (2022)

The Decision Problem for Regular First-Order Theories
von: Mathur, Umang, et al.
Veröffentlicht: (2024)

An algebraic theory of ω-regular languages, via μν-expressions
von: Das, Anupam, et al.
Veröffentlicht: (2025)

Cyclic system for an algebraic theory of alternating parity automata
von: Das, Anupam, et al.
Veröffentlicht: (2025)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
von: Rooduijn, Jan, et al.
Veröffentlicht: (2024)

A proof theory of right-linear (omega-)grammars via cyclic proofs
von: Das, Anupam, et al.
Veröffentlicht: (2024)