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

DOI10.1016/J.IPL.2016.10.005zbMATH Open1392.68194arXiv1512.04255OpenAlexW2546710019MaRDI QIDQ344560FDOQ344560

Authors: Guillermo A. Pérez 

Publication date: 23 November 2016

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

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.

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

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

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)

Cites Work

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

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)