Cover Image

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Principato, Flavio T., Esparza, Javier, Czerner, Philipp
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

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

The Black Ninjas and the Sniper: On Robustness of Population Protocols
by: Lossin, Benno, et al.
Published: (2024)

Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
by: Rote, Günter
Published: (2024)

Black-box Testing Liveness Properties of Partially Observable Stochastic Systems
by: Esparza, Javier, et al.
Published: (2023)

Temporal Causal Models as a Model of Computation
by: Gladyshev, Maksim, et al.
Published: (2026)

Efficient Learning of Weak Deterministic Büchi Automata
by: Alluwayma, Mona, et al.
Published: (2025)

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

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
by: Czerwiński, Wojciech, et al.
Published: (2025)

Approximate Problems for Finite Transducers
by: Filiot, Emmanuel, et al.
Published: (2025)

Saturation Problems for Families of Automata
by: Bohn, León, et al.
Published: (2025)

The Expansion Problem for Infinite Trees
by: Blumensath, Achim
Published: (2023)

The Similarity Control Problem with Required Events
by: Wang, Yu, et al.
Published: (2026)

On the Separability Problem of VASS Reachability Languages
by: Keskin, Eren, et al.
Published: (2024)

Computational Complexity of Alignments
by: Schwanen, Christopher T., et al.
Published: (2026)

Resynchronized Uniformization and Definability Problems for Rational Relations
by: Löding, Christof, et al.
Published: (2021)

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

Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
by: Drabik, Karolina, et al.
Published: (2025)

Separators in Continuous Petri Nets
by: Blondin, Michael, et al.
Published: (2022)

Computing measures of weak-MSO definable sets of trees
by: Niwiński, Damian, et al.
Published: (2024)

A Characterization of Turing Machines that Compute Primitive Recursive Functions
by: Schwartz, Daniel G.
Published: (2025)

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
by: Becker, Ruben, et al.
Published: (2024)

Computing Inductive Invariants of Regular Abstraction Frameworks
by: Czerner, Philipp, et al.
Published: (2024)

From Trees to Tree-Like: Distribution and Synthesis for Asynchronous Automata
by: Lehaut, Mathieu, et al.
Published: (2026)

Distribution of Reconfiguration Languages maintaining Tree-like Communication Topology
by: Hausmann, Daniel, et al.
Published: (2024)

Probabilistic Finite Automaton Emptiness is undecidable
by: Rote, Günter
Published: (2024)

Interpreted Higher-Dimensional Automata for Concurrent Discrete-Event Control
by: Bellier, Dylan, et al.
Published: (2026)

Distributional Learning of Graph Languages Generated by Fixed-Interface Clause Systems
by: Shoudai, Takayoshi, et al.
Published: (2026)

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

Efficient Interaction-Based Offline Runtime Verification of Distributed Systems with Lifeline Removal
by: Mahe, Erwan, et al.
Published: (2024)

Model Checking for Multi-Agent Systems Modeled By Epistemic Process Calculus
by: Yu, Qixian, et al.
Published: (2025)

Polyregular Model Checking
by: Lopez, Aliaume, et al.
Published: (2025)

Conservative Perception Models for Probabilistic Verification
by: Cleaveland, Matthew, et al.
Published: (2025)

Learning EFSM Models with Registers in Guards
by: Vega, Germán, et al.
Published: (2024)

Regular Languages in the Sliding Window Model
by: Ganardi, Moses, et al.
Published: (2024)

Unambiguisability and Register Minimisation of Min-Plus Models
by: Almagor, Shaull, et al.
Published: (2025)

The rIC3 Hardware Model Checker
by: Su, Yuheng, et al.
Published: (2025)

Spatio-Temporal view on the Topological Functioning Model
by: Spichkova, Maria
Published: (2025)

The Trembling-Hand Problem for LTLf Planning
by: Yu, Pian, et al.
Published: (2024)

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

A Probabilistic Model-Checking Framework for Cognitive Assessment and Training
by: De Maria, Elisabetta, et al.
Published: (2026)