Counting authorised paths in constrained control-flow graphs

Résumé

Our goal in this extended abstract is to investigate a model of computation inspired by control-flow graphs, automata and arithmetic circuits. The objective is to extend the definition of the first to include computing on nodes and edges. We are given a directed graph and a set of integer variables, with every edge in the graph being augmented in two ways. First, a set of constraints on the variables determines whether the edge is authorised. Second, to each edge is associated a function that affects the values of the variables. In this complex model, we seek to estimate the length and number of distinct paths. We restrict ourselves to the two cases in which this has meaning: when the underlying graph is a DAG, or when we have a promise that paths of infinite length do not exist in the given graph. This has varied applications, from bounding the number of execution paths in various computing models (both deterministic and non-deterministic), to counting the number of distinct stories in interactive fictions.

Publication
Proceedings of the 5th Bordeaux Graph Workshop, BGW 2019, Bordeaux, France, October 28-31, 2019