Undecidable problems in unreliable computations.

DOI10.1016/S0304-3975(02)00646-1zbMath1044.68119MaRDI QIDQ1401309

Richard Mayr

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Decidability; Counter machines; Lossy counter machines

Mathematics Subject Classification ID

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Related Items

Unnamed Item, ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS, Unnamed Item, Unnamed Item, On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words, Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\), Forward analysis and model checking for trace bounded WSTS, Reachability problems on reliable and lossy queue automata, On termination and invariance for faulty channel machines, On pebble automata for data languages with decidable emptiness problem, On the termination and structural termination problems for counter machines with incrementing errors, General decidability results for asynchronous shared-memory programs: higher-order and beyond, Reactive synthesis from interval temporal logic specifications, Parameterized verification of algorithms for oblivious robots on a ring, Computable fixpoints in well-structured symbolic model checking, Forward Analysis and Model Checking for Trace Bounded WSTS, On Pebble Automata for Data Languages with Decidable Emptiness Problem, Playing with Repetitions in Data Words Using Energy Games, Forward analysis for WSTS, part I: completions, An Approach to Computing Downward Closures, On the Reachability Analysis of Acyclic Networks of Pushdown Systems, Realizability of Real-Time Logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidable verification problems for programs with unreliable channels
• On some variants of Post's correspondence problem
• Results on the propositional \(\mu\)-calculus
• A unified approach for deciding the existence of certain petri net paths
• Unreliable channels are easier to verify than perfect channels
• Decidability of model checking for infinite-state concurrent systems
• Verifying programs with unreliable channels
• Symbolic reachability analysis of FIFO-channel systems with nonregular sets of configurations
• An Algorithm for the General Petri Net Reachability Problem
• Algebraic laws for nondeterminism and concurrency
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Infinite results