Author name cluster

Alessandro Bianco

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.

3 papers

2 author rows

TCS Journal 2012 Journal Article

Quantitatively fair scheduling

Alessandro Bianco
Marco Faella
Fabio Mogavero
Aniello Murano

We consider finite graphs whose edges are labeled with elements, called colors, taken from a fixed finite alphabet. We study the problem of determining whether there is an infinite path where either (i) all colors occur with a fixed asymptotic frequency, or (ii) there is a constant that bounds the difference between the occurrences of any two colors for all prefixes of the path. These properties can be viewed as quantitative refinements of the classical notion of fair path in a concurrent system, whose simplest form checks whether all colors occur infinitely often. Our notions provide stronger criteria, particularly suitable for scheduling applications based on a coarse-grained model of the jobs involved. In particular, they enforce a given set of priorities among the jobs involved in the system. We show that both problems we address are solvable in polynomial time, by reducing them to the feasibility of a linear program. We also consider two-player games played on finite colored graphs where the goal is one of the above frequency-related properties. For all the goals, we show that the problem of checking whether there exists a winning strategy is Co-NP-complete.

Details DOI

CSL Conference 2010 Conference Paper

Graded Computation Tree Logic with Binary Coding

Alessandro Bianco
Fabio Mogavero
Aniello Murano

Abstract Graded path quantifiers have been recently introduced and investigated as a useful framework for generalizing standard existential and universal path quantifiers in the branching-time temporal logic CTL (GCTL), in such a way that they can express statements about a minimal and conservative number of accessible paths. These quantifiers naturally extend to paths the concept of graded world modalities, which has been deeply investigated for the μ - C alculus (G μ - C alculus ) where it allows to express statements about a given number of immediately accessible worlds. As for the ”non-graded” case, it has been shown that the satisfiability problem for GCTL and the G μ - C alculus coincides and, in particular, it remains solvable in ExpTime. However, GCTL has been only investigated w. r. t. graded numbers coded in unary, while G μ - C alculus uses for this a binary coding, and it was left open the problem to decide whether the same result may or may not hold for binary GCTL. In this paper, by exploiting an automata theoretic-approach, which involves a model of alternating automata with satellites, we answer positively to this question. We further investigate the succinctness of binary GCTL and show that it is at least exponentially more succinct than G μ - C alculus.

Details

MFCS Conference 2009 Conference Paper

Balanced Paths in Colored Graphs

Alessandro Bianco
Marco Faella
Fabio Mogavero
Aniello Murano

Abstract We consider finite graphs whose edges are labeled with elements, called colors, taken from a fixed finite alphabet. We study the problem of determining whether there is an infinite path where either (i) all colors occur with the same asymptotic frequency, or (ii) there is a constant which bounds the difference between the occurrences of any two colors for all prefixes of the path. These two notions can be viewed as refinements of the classical notion of fair path, whose simplest form checks whether all colors occur infinitely often. Our notions provide stronger criteria, particularly suitable for scheduling applications based on a coarse-grained model of the jobs involved. We show that both problems are solvable in polynomial time, by reducing them to the feasibility of a linear program.

Details