### 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 Σ_{2}^{0}-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 language | English (US) |
---|---|

Title of host publication | Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings |

Pages | 254-265 |

Number of pages | 12 |

DOIs | |

State | Published - Oct 15 2013 |

Event | 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria Duration: Aug 26 2013 → Aug 30 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8087 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 |
---|---|

Country | Austria |

City | Klosterneuburg |

Period | 8/26/13 → 8/30/13 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings*(pp. 254-265). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087 LNCS). https://doi.org/10.1007/978-3-642-40313-2_24