CIAA2003

START ConferenceManager

New Complexity Results for Some Linear Counting Problems Using Minimal Solutions to Linear Diophantine Equations

Gaoyan Xie, Cheng Li, Zhe Dang

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

The linear reachability problem is to decide whether there is an execution path in a given finite state transition system such that the counts of labels on the path satisfy a given linear constraint. Using results on minimal solutions (in nonnegative integers) for linear Diophantine systems, we obtain new complexity results for the problem, as well as other linear counting problems for finite state transition systems and timed automata. In contrast to previously known results, the complexity bounds obtained in this paper are polynomial in the size of the transition system in consideration, when the linear constraint is fixed.