Author name cluster

Paul Hunter

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2018 Journal Article

Mean-payoff games with partial observation

Paul Hunter
Arno Pauly
Guillermo A. Pérez
Jean-François Raskin

Mean-payoff games are important quantitative models for open reactive systems. They have been widely studied as games of full observation. In this paper we investigate the algorithmic properties of several sub-classes of mean-payoff games where the players have asymmetric information about the state of the game. These games are in general undecidable and not determined according to the classical definition. We show that such games are determined under a more general notion of winning strategy. We also consider mean-payoff games where the winner can be determined by the winner of a finite cycle-forming game. This yields several decidable classes of mean-payoff games of asymmetric information that require only finite-memory strategies, including a generalization of full-observation games where positional strategies are sufficient. We give an exponential time algorithm for determining the winner of the latter.

Details DOI

Highlights Conference 2015 Conference Abstract

Reachability in succinct one-counter games

Paul Hunter

We consider two-player games with reachability objectives played on transition systems of succinct one-counter machines, that is, machines where the counter is incremented or decremented by a value given in binary. We show that the reachability and counter reachability problems are equivalent, in contrast to non-succinct games and that all problems are EXPSPACE-complete.

Details

Highlights Conference 2013 Conference Abstract

The expressive completeness of Metric Temporal Logic

Paul Hunter

LTL has emerged as the primary logic for specifying temporal properties. This is largely due to the low complexity of its associated model checking problem and its high expressibility - with the celebrated result of Kamp showing that LTL has the same expressive power as first-order logic. In the quantitative setting, Metric Temporal Logic is quickly becoming the standard to which all other temporal logics are compared. It turns out that the expressive power of MTL is dependent on the set of constants available, and I will give a precise characterization of when MTL has the same expressive power as first-order logic.

PDF Details

TCS Journal 2008 Journal Article

Digraph measures: Kelly decompositions, games, and orderings

Paul Hunter
Stephan Kreutzer

We consider various well-known, equivalent complexity measures for graphs such as elimination orderings, k -trees and cops and robber games and study their natural translations to digraphs. We show that on digraphs the translations of these measures are also equivalent and induce a natural connectivity measure. We introduce a decomposition for digraphs and an associated width, Kelly-width, which is equivalent to the aforementioned measure. We demonstrate its usefulness by exhibiting potential applications including polynomial-time algorithms for NP-complete problems on graphs of bounded Kelly-width, and complexity analysis of asymmetric matrix factorization. Finally, we compare the new width to other known decompositions of digraphs.

Details DOI