License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.10
URN: urn:nbn:de:0030-drops-95481
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9548/
Go to the corresponding LIPIcs Volume Portal

Michaliszyn, Jakub ; Otop, Jan

Non-deterministic Weighted Automata on Random Words

pdf-format:
LIPIcs-CONCUR-2018-10.pdf (0.5 MB)

Abstract

We present the first study of non-deterministic weighted automata under probabilistic semantics. In this semantics words are random events, generated by a Markov chain, and functions computed by weighted automata are random variables. We consider the probabilistic questions of computing the expected value and the cumulative distribution for such random variables.
The exact answers to the probabilistic questions for non-deterministic automata can be irrational and are uncomputable in general. To overcome this limitation, we propose an approximation algorithm for the probabilistic questions, which works in exponential time in the automaton and polynomial time in the Markov chain. We apply this result to show that non-deterministic automata can be effectively determinised with respect to the standard deviation metric.

BibTeX - Entry

@InProceedings{michaliszyn_et_al:LIPIcs:2018:9548,
  author =	{Jakub Michaliszyn and Jan Otop},
  title =	{{Non-deterministic Weighted Automata on Random Words}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9548},
  URN =		{urn:nbn:de:0030-drops-95481},
  doi =		{10.4230/LIPIcs.CONCUR.2018.10},
  annote =	{Keywords: quantitative verification, weighted automata, expected value}
}

Keywords: quantitative verification, weighted automata, expected value
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI