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

DOI10.1016/j.ipl.2016.10.005zbMath1392.68194arXiv1512.04255OpenAlexW2546710019MaRDI QIDQ344560

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

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

Related Items (3)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• The complexity of mean payoff games on graphs
• Complexity Hierarchies beyond Elementary
• Generalized Mean-payoff and Energy Games
• Mean-Payoff Games with Partial-Observation
• 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
• Hierarchies of number-theoretic functions. I
• A classification of the ordinal recursive functions

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