Pushing undecidability of the isolation problem for probabilistic automata

2011/04/14 by Nathanaël Fijalkow, Fijalkow, Nathanaël, Hugo Gimbert +3 · 1 citation
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Software Reliability and Analysis Research #cs.FL #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1104.3054

arxiv created 2011/04/14 · openalex publication_date 2011/04/14 · arxiv updated 2011/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable for general probabilistic automata, without restriction on the number of probabilistic transitions. In this note, we develop a simulation technique that allows to simulate any probabilistic automaton with one having only one probabilistic transition.

Cited by

• Deciding the Value 1 Problem of Probabilistic Leaktight Automata

Related

• Two Recursively Inseparable Problems for Probabilistic Automata
• When is Containment Decidable for Probabilistic Automata?
• Probabilistic Finite Automaton Emptiness is undecidable
• Deciding the Value 1 Problem of Probabilistic Leaktight Automata
• Decidability of cutpoint isolation for probabilistic finite automata on\n letter-bounded inputs