Complexity of modal logics with Presburger constraints

Afanasiev, 2005, PDL for ordered trees, Journal of Applied Non-Classical Logics, 15, 115, 10.3166/jancl.15.115-135 Alechina, 2003, A modal perspective on path constraints, Journal of Logic and Computation, 13, 939, 10.1093/logcom/13.6.939 Alur, 1994, A really temporal logic, Journal of the Association for Computing Machinery, 41, 181, 10.1145/174644.174651 L. Berman, Precise bounds for Presburger arithmetic and the reals with addition: Preliminary report, in: FOCS'77, 1977, pp. 95–99 Bidoit, 2004, A first step towards modeling semistructured data in hybrid multimodal logic, Journal of Applied Non-Classical Logics, 14, 447, 10.3166/jancl.14.447-475 Blackburn, 2001 Bonatti, 2004, On the undecidability of logics with converse, nominals, recursion and counting, Artificial Intelligence, 158, 75, 10.1016/j.artint.2004.04.012 Boneva, 2005, Automata and logics for unranked and unordered trees, vol. 3467, 500 Borosh, 1976, Bounds on positive integral solutions of linear diophantine equations, American Mathematical Society, 55, 299, 10.1090/S0002-9939-1976-0396605-3 Bradfield, 2007, Modal mu-calculi, 721 Calvanese, 2005, Expressive description logics, 178 Cerrato, 1990, General canonical models for graded normal logics, Studia Logica, 49, 242, 10.1007/BF00935601 Cerrato, 1994, Decidability by filtrations for graded normal logics (graded modalities V), Studia Logica, 53, 61, 10.1007/BF01053022 Dal Zilio, 2003, XML schema, tree logic and sheaves automata, vol. 2706, 246 Dal Zilio, 2006, XML schema, tree logic and sheaves automata, Applicable Algebra in Engineering, Communication and Computing, 17, 337, 10.1007/s00200-006-0016-7 Demri Demri, 2003, A polynomial space construction of tree-like models for logics with local chains of modal connectives, Theoretical Computer Science, 300, 235, 10.1016/S0304-3975(02)00082-8 Demri, 2006, Presburger modal logic is PSPACE-complete, vol. 4130, 541 Fattorosi Barnaba, 1985, Graded modalities, Studia Logica, 44, 197, 10.1007/BF00379767 Fine, 1972, In so many possible worlds, Notre Dame Journal of Formal Logic, 13, 516, 10.1305/ndjfl/1093890715 Fischer, 1979, Propositional dynamic logic of regular programs, Journal of Computer and System Sciences, 18, 194, 10.1016/0022-0000(79)90046-1 Fischer, 1974, Super-exponential complexity of Presburger arithmetic, vol. 7, 27 Fitting, 1983 Goré, 1999, Tableaux methods for modal and temporal logics, 297 Hemaspaandra, 2001, The complexity of poor man's logic, Journal of Logic and Computation, 11, 609, 10.1093/logcom/11.4.609 B. Hollunder, F. Baader, Qualifying number restrictions in concept languages, in: KR'91, 1991, pp. 335–346 Horrocks, 2000, Reasoning with individuals for the description logic SHIQ, vol. 1831, 482 Kazakov, 2004, A polynomial translation from the two-variable guarded fragment with number restrictions to the guarded fragment, vol. 3229, 372 Kupferman, 2002, The complexity of the graded μ-calculus, vol. 2392, 423 Ladner, 1977, The computational complexity of provability in systems of modal propositional logic, SIAM Journal of Computing, 6, 467, 10.1137/0206033 Marx, 2003, XPath and modal logics of finite DAG's, vol. 2796, 150 Moller, 2003, Counting on CTL*: on the expressive power of monadic path logic, Information and Computation, 184, 147, 10.1016/S0890-5401(03)00104-4 A. Montanari, A. Policriti, A set-theoretic approach to automated deduction in graded modal logics, in: IJCAI'97, 1997, pp. 196–201 Ohlbach, 1996, Translating graded modalities into predicate logics, 253 Ohsaki, 2005, Monotone AC-tree automata, vol. 3835, 337 Pacuit, 2004, Majority logic, 598 Papadimitriou, 1981, On the complexity of integer programming, Journal of the Association for Computing Machinery, 28, 765, 10.1145/322276.322287 Rackoff, 1978, The covering and boundedness problems for vector addition systems, Theoretical Computer Science, 6, 223, 10.1016/0304-3975(78)90036-1 Reynolds, 2002, Separation logic: a logic for shared mutable data structures, 55 Schröder, 2006, PSPACE bounds for rank-1 modal logics, 231 Seidl, 2007, Counting in trees, Texts in Logic and Games, 2, 575 Seidl, 2004, Counting in trees for free, vol. 3142, 1136 Spaan, 1993, The complexity of propositional tense logics, 287 Tobies, 2001, PSPACE reasoning for graded modal logics, Journal of Logic and Computation, 11, 85, 10.1093/logcom/11.1.85 van der Hoek, 1992, On the semantics of graded modalities, Journal of Applied Non-Classical Logics, 2, 81 van der Hoek, 1995, Counting objects, Journal of Logic and Computation, 5, 325, 10.1093/logcom/5.3.325 van der Hoek, 1991, Graded modalities in epistemic logic, Logique et Analyse, 133–134, 251 Wolper, 1983, Temporal logic can be more expressive, Information and Computation, 56, 72