The complexity of the equivalence problem for two characterizations of Presburger sets
type: Item
instance of: scholarly article
title: The complexity of the equivalence problem for two characterizations of Presburger sets
zbMATH Open document ID: 0454.03005
DOI: 10.1016/S0304-3975(81)80003-5
author: Eitan M. Gurari
author: Oscar H. Ibarra
published in: Theoretical Computer Science
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 3710145
zbMATH Keywords: Presburger formulas
zbMATH Keywords: reversal-bounded multicounter machines
zbMATH Keywords: upper bound
zbMATH Keywords: deterministic time complexity
zbMATH Keywords: inequivalence problem
zbMATH Keywords: semilinear sets
zbMATH Keywords: Presburger relations
MaRDI profile type: Publication
cites work: Reversal-bounded multipushdown machines
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations
cites work: The complexity of theorem-proving procedures
cites work: Q4082296
cites work: Hierarchies of complete problems
cites work: Semigroups, Presburger formulas, and languages
cites work: Simple counter machines and number-theoretic problems
cites work: An NP-complete number-theoretic problem
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: Q4142699
cites work: A characterization of semilinear sets
cites work: A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
cites work: Q4091421
description: scientific article; zbMATH DE number 3710145