License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.38
URN: urn:nbn:de:0030-drops-155495
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15549/
Go to the corresponding LIPIcs Volume Portal

Boker, Udi ; Lehtinen, Karoliina

History Determinism vs. Good for Gameness in Quantitative Automata

pdf-format:
LIPIcs-FSTTCS-2021-38.pdf (0.8 MB)

Abstract

Automata models between determinism and nondeterminism/alternations can retain some of the algorithmic properties of deterministic automata while enjoying some of the expressiveness and succinctness of nondeterminism. We study three closely related such models - history determinism, good for gameness and determinisability by pruning - on quantitative automata.
While in the Boolean setting, history determinism and good for gameness coincide, we show that this is no longer the case in the quantitative setting: good for gameness is broader than history determinism, and coincides with a relaxed version of it, defined with respect to thresholds. We further identify criteria in which history determinism, which is generally broader than determinisability by pruning, coincides with it, which we then apply to typical quantitative automata types.
As a key application of good for games and history deterministic automata is synthesis, we clarify the relationship between the two notions and various quantitative synthesis problems. We show that good-for-games automata are central for "global" (classical) synthesis, while "local" (good-enough) synthesis reduces to deciding whether a nondeterministic automaton is history deterministic.

BibTeX - Entry

@InProceedings{boker_et_al:LIPIcs.FSTTCS.2021.38,
  author =	{Boker, Udi and Lehtinen, Karoliina},
  title =	{{History Determinism vs. Good for Gameness in Quantitative Automata}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15549},
  URN =		{urn:nbn:de:0030-drops-155495},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.38},
  annote =	{Keywords: Good for games, history determinism, alternation, quantitative automata}
}

Keywords: Good for games, history determinism, alternation, quantitative automata
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

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