TY - GEN

T1 - Expressivity of time-varying graphs

AU - Casteigts, Arnaud

AU - Flocchini, Paola

AU - Godard, Emmanuel

AU - Santoro, Nicola

AU - Yamashita, Masafumi

PY - 2013

Y1 - 2013

N2 - Time-varying graphs model in a natural way infrastructure-less highly dynamic systems, such as wireless ad-hoc mobile networks, robotic swarms, vehicular networks, etc. In these systems, a path from a node to another might still exist over time, rendering computing possible, even though at no time the path exists in its entirety. Some of these systems allow waiting (i.e., provide the nodes with store-carry-forward-like mechanisms such as local buffering) while others do not. In this paper, we focus on the structure of the time-varying graphs modelling these highly dynamical environments. We examine the complexity of these graphs, with respect to waiting, in terms of their expressivity; that is in terms of the language generated by the feasible journeys (i.e., the "paths over time"). We prove that the set of languages Lnowait when no waiting is allowed contains all computable languages. On the other end, using algebraic properties of quasi-orders, we prove that Lwait is just the family of regular languages, even if the presence of edges is controlled by some arbitrary function of the time. In other words, we prove that, when waiting is allowed, the power of the accepting automaton drops drastically from being as powerful as a Turing machine, to becoming that of a Finite-State machine. This large gap provides a measure of the impact of waiting. We also study bounded waiting; that is when waiting is allowed at a node for at most d time units. We prove that Lwait[d] = Lnowait; that is, the complexity of the accepting automaton decreases only if waiting is unbounded.

AB - Time-varying graphs model in a natural way infrastructure-less highly dynamic systems, such as wireless ad-hoc mobile networks, robotic swarms, vehicular networks, etc. In these systems, a path from a node to another might still exist over time, rendering computing possible, even though at no time the path exists in its entirety. Some of these systems allow waiting (i.e., provide the nodes with store-carry-forward-like mechanisms such as local buffering) while others do not. In this paper, we focus on the structure of the time-varying graphs modelling these highly dynamical environments. We examine the complexity of these graphs, with respect to waiting, in terms of their expressivity; that is in terms of the language generated by the feasible journeys (i.e., the "paths over time"). We prove that the set of languages Lnowait when no waiting is allowed contains all computable languages. On the other end, using algebraic properties of quasi-orders, we prove that Lwait is just the family of regular languages, even if the presence of edges is controlled by some arbitrary function of the time. In other words, we prove that, when waiting is allowed, the power of the accepting automaton drops drastically from being as powerful as a Turing machine, to becoming that of a Finite-State machine. This large gap provides a measure of the impact of waiting. We also study bounded waiting; that is when waiting is allowed at a node for at most d time units. We prove that Lwait[d] = Lnowait; that is, the complexity of the accepting automaton decreases only if waiting is unbounded.

UR - http://www.scopus.com/inward/record.url?scp=84883197373&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883197373&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40164-0_12

DO - 10.1007/978-3-642-40164-0_12

M3 - Conference contribution

AN - SCOPUS:84883197373

SN - 9783642401633

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 95

EP - 106

BT - Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings

T2 - 19th International Symposium on Fundamentals of Computation Theory, FCT 2013

Y2 - 19 August 2013 through 21 August 2013

ER -