Source author record

Carlo Comin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory Formal Languages and Automata Theory Artificial Intelligence Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

7works

6topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

An Improved Pseudo-Polynomial Upper Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games

In this work we offer an $O(|V|^2 |E|\, W)$ pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor $\log(|V|\, W)$ the best previously known pseudo-polynomial time upper bound due to Brim,~\etal The improvement hinges on a suitable characterization of values, and a description of optimal positional strategies, in terms of reweighted Energy Games and Small Energy-Progress Measures.

preprint2016arXiv

Energy Structure of Optimal Positional Strategies in Mean Payoff Games

This note studies structural aspects concerning Optimal Positional Strategies (OPSs) in Mean Payoff Games (MPGs), it is a contribution to understanding the relationship between OPSs in MPGs and Small Energy-Progress Measures (SEPMs) in reweighted Energy Games (EGs). Firstly, it is observed that the space of all OPSs, $\texttt{opt}_ΓΣ^M_0$ , admits a unique complete decomposition in terms of so-called extremal-SEPM{s} in reweighted EG{s}; this points out what we called the "Energy-Lattice $\mathcal{X}^*_Γ$ of $\texttt{opt}_ΓΣ^M_0$ ". Secondly, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of $\mathcal{X}^*_Γ$ , and for computing the corresponding partitioning of $\texttt{opt}_ΓΣ^M_0$ . It is observed that the corresponding recursion tree defines an additional lattice $\mathcal{B}^*_Γ$ , whose elements are certain subgames $Γ'\subseteq Γ$ that we call basic subgames. The extremal-SEPMs of a given \MPG $Γ$ coincide with the least-SEPMs of the basic subgames of $Γ$ ; so, $\mathcal{X}^*_Γ$ is the energy-lattice comprising all and only the least-SEPMs of the \emph{basic} subgames of $Γ$ . The complexity of the proposed enumeration for both $\mathcal{B}^*_Γ$ and $\mathcal{X}^*_Γ$ is $O(|V|^3|E|W |\mathcal{B}^*_Γ|)$ total time and $O(|V||E|)+Θ\big(|E| \mathcal{B}^*_Γ|\big)$ working space. Finally, it is constructed an \MPG $Γ$ for which $|\mathcal{B}^*_Γ| > |\mathcal{X}^*_Γ|$ , this proves that $\mathcal{B}^*_Γ$ and $\mathcal{X}^*_Γ$ are not isomorphic.

preprint2016arXiv

Faster O(|V|^2|E|W)-Time Energy Algorithms for Optimal Strategy Synthesis in Mean Payoff Games

This study strengthens the links between Mean Payoff Games (\MPG{s}) and Energy Games (EG{s}). Firstly, we offer a faster $O(|V|^2|E|W)$ pseudo-polynomial time and $Θ(|V|+|E|)$ space deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in \MPG{s}. This improves the best previously known estimates on the pseudo-polynomial time complexity to: $O(|E|\log |V|) + Θ\Big(\sum_{v\in V}\texttt{deg}_Γ(v)\cdot\ell_Γ(v)\Big) = O(|V|^2|E|W),$ where $\ell_Γ(v)$ counts the number of times that a certain energy-lifting operator $δ(\cdot, v)$ is applied to any $v\in V$ , along a certain sequence of Value-Iterations on reweighted \EG{s}; and $\texttt{deg}_Γ(v)$ is the degree of $v$ . This improves significantly over a previously known pseudo-polynomial time estimate, i.e. $Θ\big(|V|^2|E|W + \sum_{v\in V}\texttt{deg}_Γ(v)\cdot\ell_Γ(v)\big)$ \citep{CR15, CR16}, as the pseudo-polynomiality is now confined to depend solely on $\ell_Γ$ . Secondly, we further explore on the relationship between Optimal Positional Strategies (OPSs) in \MPG{s} and Small Energy-Progress Measures (SEPMs) in reweighted \EG{s}. It is observed that the space of all OPSs, $\texttt{opt}_ΓΣ^M_0$ , admits a unique complete decomposition in terms of extremal-SEPM{s} in reweighted EG{s}. This points out what we called the "Energy-Lattice $\mathcal{X}^*_Γ$ associated to $\texttt{opt}_ΓΣ^M_0$ ". Finally, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of $\mathcal{X}^*_Γ$ , and for computing the corresponding partitioning of $\texttt{opt}_ΓΣ^M_0$ .

preprint2015arXiv

An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication

The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et.al. in 1977. As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e. maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama showed it is $O(mn)$ . In 2004, Makino and Uno sharpened the time delay to $O(n^ω)$ by generating all the children of a node in one single shot performed by computing a \emph{square} fast matrix multiplication. In this paper, we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings' computation even further. Our idea is to rely on rectangular fast matrix multiplication in order to compute all children of $n^2$ nodes in one shot. According to the current upper bounds on fast matrix multiplication, with this the time delay improves from $O(n^{2.3728639})$ to $O(n^{2.093362})$ .

preprint2015arXiv

Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking

Conditional Simple Temporal Network (CSTN) is a constraint-based graph-formalism for conditional temporal planning. It offers a more flexible formalism than the equivalent CSTP model of Tsamardinos, Vidal and Pollack, from which it was derived mainly as a sound formalization. Three notions of consistency arise for CSTNs and CSTPs: weak, strong, and dynamic. Dynamic consistency is the most interesting notion, but it is also the most challenging and it was conjectured to be hard to assess. Tsamardinos, Vidal and Pollack gave a doubly-exponential time algorithm for deciding whether a CSTN is dynamically-consistent and to produce, in the positive case, a dynamic execution strategy of exponential size. In the present work we offer a proof that deciding whether a CSTN is dynamically-consistent is coNP-hard and provide the first singly-exponential time algorithm for this problem, also producing a dynamic execution strategy whenever the input CSTN is dynamically-consistent. The algorithm is based on a novel connection with Mean Payoff Games, a family of two-player combinatorial games on graphs well known for having applications in model-checking and formal verification. The presentation of such connection is mediated by the Hyper Temporal Network model, a tractable generalization of Simple Temporal Networks whose consistency checking is equivalent to determining Mean Payoff Games. In order to analyze the algorithm we introduce a refined notion of dynamic-consistency, named ε-dynamic-consistency, and present a sharp lower bounding analysis on the critical value of the reaction time \hat{\varepsilon} where the CSTN transits from being, to not being, dynamically-consistent. The proof technique introduced in this analysis of \hat{\varepsilon} is applicable more in general when dealing with linear difference constraints which include strict inequalities.

preprint2013arXiv

(Extended Version) Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata

We study a model of one-way quantum automaton where only measurement operations are allowed ($\mon$). We give an algebraic characterization of $\lmo(Σ)$, showing that the syntactic monoids of the languages in $\lmo(Σ)$ are exactly the $J$ -trivial literally idempotent syntactic monoids, where $J$ is the Green's relation determined by two-sided ideals. We also prove that $\lmo(Σ)$ coincides with the literal variety of literally idempotent piecewise testable regular languages. This allows us to prove the existence of a polynomial time algorithm for deciding whether a regular language belongs to $\lmo(Σ)$ and to discuss definability issues in terms of the existential first-order logic $Σ_1[<]$ and the linear temporal logic without the next operator LTLWN.

preprint2012arXiv

Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata

We study a model of one-way quantum automaton where only measurement operations are allowed (MOn-1qfa). We give an algebraic characterization of LMO, showing that the syntactic monoids of the languages in LMO are exactly the literal pseudovariety of J-trivial literally idempotent monoids, where J is the Green's relation determined by two-sided ideals. We also prove that LMO coincides with the literal variety of literally idempotent piecewise testable regular languages. This allows us to prove the existence of a polynomial time algorithm for deciding whether a regular language belongs to LMO.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Carlo Comin

Research overview

Is this your work?

7 publications

An Improved Pseudo-Polynomial Upper Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games

Energy Structure of Optimal Positional Strategies in Mean Payoff Games

Faster O(|V|^2|E|W)-Time Energy Algorithms for Optimal Strategy Synthesis in Mean Payoff Games

An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication

Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking

(Extended Version) Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata

Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata

See the researcher in context

Building this map preview