The complexity of the equivalence problem for counter machines, semilinear sets, and simple programs
- 1 January 1979
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 142-152
- https://doi.org/10.1145/800135.804407
Abstract
It is shown that the class of relations (functions) definable by Presburger formulas is exactly the class of relations (functions) computable by finite-reversal multicounter machines. An upper bound of 2c(N/logN)4 on the deterministic time complexity of the equivalence problem for such machines is established. In fact, it is proved that the inequivalence problem is NP-complete. These results are used to derive some upper bounds on the complexity of the equivalence problem for semilinear sets and simple programs. For example, it is shown that the equivalence problem for semilinear sets (these sets are exactly the Presburger relations) is decidable in deterministic time 22cN2. A class of programs which realize exactly the relations (functions) definable by Presburger formulas is shown to have an NP-complete inequivalence problem. Hence, its equivalence problem is decidable in deterministic time 2p(N). This bound is a four-level exponential improvement over a previously known result.This publication has 0 references indexed in Scilit: