@inproceedings{10.1007/978-3-662-46678-0_24,
    Abstract = {We consider Presburger arithmetic (PA) extended with modulo counting quantifiers. We show that its complexity is essentially the same as that of PA, i.e., we give a doubly exponential space bound. This is done by giving and analysing a quantifier elimination procedure similar to Reddy and Loveland's procedure for PA. We also show that the complexity of the automata-based decision procedure for PA with modulo counting quantifiers has the same triple-exponential time complexity as the one for PA when using least significant bit first encoding.},
    Address = {Berlin, Heidelberg},
    Author = {Habermehl, Peter and Kuske, Dietrich},
    BookTitle = {Foundations of Software Science and Computation Structures},
    Editor = {Pitts, Andrew},
    File = {Habermehl-Kuske2015\_Chapter\_OnPresburgerArithmeticExtended (0) - a - a - a.pdf},
    ISBN = {978-3-662-46678-0},
    Pages = {375--389},
    Publisher = {Springer Berlin Heidelberg},
    Title = {On Presburger Arithmetic Extended with Modulo Counting Quantifiers},
    Year = {2015},
    date-added = {2019-07-11 20:41:09 +0100},
    date-modified = {2019-07-11 20:41:09 +0100},
    doi = {10.1007/978-3-662-46678-0_24}
}

@inproceedings{10.1007/978-3-662-46678-0_24, Abstract = {We consider Presburger arithmetic (PA) extended with modulo counting quantifiers. We show that its complexity is essentially the same as that of PA, i.e., we give a doubly exponential space bound. This is done by giving and analysing a quantifier elimination procedure similar to Reddy and Loveland's procedure for PA. We also show that the complexity of the automata-based decision procedure for PA with modulo counting quantifiers has the same triple-exponential time complexity as the one for PA when using least significant bit first encoding.}, Address = {Berlin, Heidelberg}, Author = {Habermehl, Peter and Kuske, Dietrich}, BookTitle = {Foundations of Software Science and Computation Structures}, Editor = {Pitts, Andrew}, File = {Habermehl-Kuske2015_Chapter_OnPresburgerArithmeticExtended (0) - a - a - a.pdf}, ISBN = {978-3-662-46678-0}, Pages = {375--389}, Publisher = {Springer Berlin Heidelberg}, Title = {On Presburger Arithmetic Extended with Modulo Counting Quantifiers}, Year = {2015}, date-added = {2019-07-11 20:41:09 +0100}, date-modified = {2019-07-11 20:41:09 +0100}, doi = {10.1007/978-3-662-46678-0_24} }