The Library
When is containment decidable for probabilistic automata?
Tools
Tools
Tools
Daviaud, Laure, Jurdzinski, Marcin, Lazic, Ranko, Mazowiecki, Filip, Pérez, Guillermo A. and Worell, James (2018) When is containment decidable for probabilistic automata? In: ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9-13 Jul 2018. Published in: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), 107 121:1-121:14. ISBN 9783959770767. doi:10.4230/LIPIcs.ICALP.2018.121
|
PDF
WRAP-when-containment-decidable-probabilistic-automata-Daviaud-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1024Kb) | Preview |
Official URL: http://doi.org/10.4230/LIPIcs.ICALP.2018.121
Abstract
The containment problem for quantitative automata is the natural quantitative generalisation of the classical language inclusion problem for Boolean automata. We study it for probabilistic automata, where it is known to be undecidable in general. We restrict our study to the class of probabilistic automata with bounded ambiguity. There, we show decidability (subject to Schanuel's conjecture) when one of the automata is assumed to be unambiguous while the other one is allowed to be finitely ambiguous. Furthermore, we show that this is close to the most general decidable fragment of this problem by proving that it is already undecidable if one of the automata is allowed to be linearly ambiguous.
| Item Type: | Conference Item (Paper) | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Machine theory, Algorithms | ||||||||||||||||||
| Journal or Publication Title: | 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) | ||||||||||||||||||
| Publisher: | Leibniz | ||||||||||||||||||
| ISBN: | 9783959770767 | ||||||||||||||||||
| Official Date: | 4 July 2018 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Volume: | 107 | ||||||||||||||||||
| Page Range: | 121:1-121:14 | ||||||||||||||||||
| Article Number: | 379 | ||||||||||||||||||
| DOI: | 10.4230/LIPIcs.ICALP.2018.121 | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||
| Date of first compliant deposit: | 4 May 2018 | ||||||||||||||||||
| Date of first compliant Open Access: | 4 May 2018 | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||
| Conference Paper Type: | Paper | ||||||||||||||||||
| Title of Event: | ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming | ||||||||||||||||||
| Type of Event: | Conference | ||||||||||||||||||
| Location of Event: | Prague, Czech Republic | ||||||||||||||||||
| Date(s) of Event: | 9-13 Jul 2018 | ||||||||||||||||||
| Related URLs: | |||||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
