Probabilistic automata with isolated cut-points

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider various decision problems for probabilistic finite automata (PFA)s with isolated cut-points. Recall that a cut-point x is said to be isolated for a PFA if the acceptance probability of all finite strings is bounded away from x. First we establish the exact level of undecidability of the problem of determining if a cut-point is isolated; we show this problem to be Σ20-complete. Next we introduce a new class of PFAs called eventually weakly ergodic PFAs that generalize ergodic and weakly ergodic PFAs. We show that the emptiness and universality problem for these PFAs is decidable provided the cut-point is isolated.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings
Pages254-265
Number of pages12
DOIs
StatePublished - Oct 15 2013
Event38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria
Duration: Aug 26 2013Aug 30 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8087 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
CountryAustria
CityKlosterneuburg
Period8/26/138/30/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Probabilistic automata with isolated cut-points'. Together they form a unique fingerprint.

Cite this