5 citations · 13 across the 12 of their papers we have counts for
4 papers · 1 filter
Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics
Romeo Rizzi, Massimo Cairo, Veli Mäkinen +2
Covering alignment problems arise from recent developments in genomics; so called pan-genome graphs are replacing reference genomes, and advances in haplotyping enable full content…
Dynamic Controllability of Conditional Simple Temporal Networks is PSPACE-complete
Massimo Cairo, Romeo Rizzi
Even after the proposal of various solution algorithms, the precise computational complexity of checking whether a Conditional Temporal Network is Dynamically Controllable had stil…
Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks -- Extended version with an Improved Upper Bound --
Massimo Cairo, Carlo Comin, Romeo Rizzi
CSTNs is a constraint-based graph-formalism for conditional temporal planning. In order to address the DC-Checking problem, in [Comin and Rizzi, TIME 2015] we introduced epsilon-DC…
The Complexity of Simulation and Matrix Multiplication
Massimo Cairo, Romeo Rizzi
Computing the simulation preorder of a given Kripke structure (i.e., a directed graph with labeled vertices) has crucial applications in model checking of temporal logic. It am…