Transactions of the American Mathematical Society · 1984 · 61 citations · 7 references
ComputingComputer ScienceMathematicsAlgebraLogicTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityStructural ComplexityArithmetic Formula Lower BoundsFormula ComplexityLower BoundsQuantifier EliminationSimple Structure
We consider formula subclasses of Presburger arithmetic which have a simple structure in one sense or the other and investigate their computational complexity. We also prove some results on the lower bounds of lengths of formulas which are related to questions on quantifier elimination.
7