The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete

DOI10.1016/J.IPL.2016.10.005MaRDI QIDQ344560zbMATH OpenOpenAlexFDO

Authors Guillermo A. Pérez

Publication date 23 November 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.04255

zbMATH Keywords

game theoryformal methodspartial observationreactive synthesis

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05)

Abstract: In this paper we study two-player games with asymmetric partial observation and an energy objective. Such games are played on a weighted automaton by Eve, choosing actions, and Adam, choosing a transition labelled with the given action. Eve attempts to maintain the sum of the weights (of the transitions taken) non-negative while Adam tries to do the opposite. Eve does not know the exact state of the game, she is only given an equivalence class of states which contains it. In contrast, Adam has full observation. We show the fixed initial credit problem for these games is Ack-complete.

Recommendations

• Energy and mean-payoff games with imperfect information
• The complexity of partial-observation parity games
• Energy parity games
• Energy parity games
• Mean-payoff games with partial observation

Cites work

• scientific article; zbMATH DE number 5869590 (Why is no real title available?)
• scientific article; zbMATH DE number 1215495 (Why is no real title available?)
• A classification of the ordinal recursive functions
• Complexity hierarchies beyond elementary
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Energy and mean-payoff games with imperfect information
• Fixed-dimensional energy games are in pseudo-polynomial time
• Generalized mean-payoff and energy games
• Hierarchies of number-theoretic functions. I
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Mean-payoff games with partial-observation (extended abstract)
• The complexity of mean payoff games on graphs

Cited in

(3)

• Enforcing opacity by insertion functions under multiple energy constraints
• The Parametric Complexity of Lossy Counter Machines
• Optimal supervisory control with mean payoff objectives and under partial observation

This page was built for publication: The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344560)