Computer Laboratory

Selected Publications

  1. M. Anderson, A. Dawar. On Symmetric Circuits and Fixed-Point Logics, STACS 2014. A full version is here
  2. A. Dawar, E. Grädel, B. Holm, E. Kopczynski, W. Pakusa. Definability of Linear Equation Systems over Groups and Rings. Logical Methods in Computer Science 9-(4:12) (2013).
  3. M. Anderson, A. Dawar, B. Holm. Maximum Matching and Linear Programming in Fixed-Point Logic with Counting. (extended abstract in LICS 2013).
  4. D. Berwanger, A. Dawar, P. Hunter, S. Kreutzer, J. Obdrzálek. The DAG-width of Directed Graphs. J. Comb. Theory, Ser. B 102 (2012), 900-923.
  5. A. Atserias, A. Dawar. Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. (extended abstract in ICALP 2012).
  6. A. Dawar, B. Holm. Pebble Games with Algebraic Rules (extended abstract in ICALP 2012).
  7. A. Bouland, A. Dawar, E. Kopczynski. On Tractable Parameterizations of Graph Isomorphism. IPEC 2012, Lecture Notes in Computer Science vol. 7535, Springer-Verlag (2012), 218-230.
  8. A. Dawar, Homomorphism Preservation on Quasi-Wide Classes, Journal of Computer and System Sciences, 76 (2010), 324-332.
  9. A. Dawar and E. Grädel Properties of Almost All Graphs and Generalized Quantifiers, Fundamenta Informaticae, 98 (2010), 351-372.
  10. A. Dawar and S. Kreutzer, Domination Problems in Nowhere-Dense Classes of Graphs, Proc. 29th Conf. on Foundations of Software Technology and Theoretical Computer Science, (2009).
  11. A. Dawar and M. Otto, Modal Characterisation Theorems over Special Classes of Frames Annals of Pure and Applied Logic, 161 (2009), 1-42.
  12. A. Dawar and Y. He, Parameterized Complexity Classes under Logical Reductions, Proc. 34th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science vol. 5734, Springer-Verlag (2009), 258-269.
  13. A. Dawar, M. Grohe, B. Holm and B. Laubner, Logics with Rank Operators Proc. 24th IEEE Symp. on Logic in Computer Science, IEEE Computer Society Press (2009).
  14. A. Atserias, A. Bulatov and A. Dawar Affine Systems of Equations and Counting Infinitary Logic, Theoretical Computer Science 410 (2009), 1666-1683.
  15. T. Antonopoulos and A. Dawar, Separating Graph Logic from MSO FoSSaCS'09: Foundations of Software Science and Computation Structures, Lecture Notes in Computer Science vol. 5504, Springer-Verlag (2009), 63-77.
  16. A. Atserias, A. Dawar and M. Grohe, Preservation under Extensions on Well-behaved Finite Structures SIAM J. on Computing, 38 (2008), 1364-1381.
  17. A. Dawar and E. Grädel The Descriptive Complexity of Parity Games, CSL'08: Computer Science and Logic Lecture Notes in Computer Science vol. 5213, Springer-Verlag (2008), 353-367.
  18. A. Dawar and S. Kreutzer On Datalog vs. LFP, Proc. 35th International Colloquium on Automata, Languages and Programming - ICALP'08, Lecture Notes in Computer Science vol. 5126, Springer-Verlag (2008), 160-171.
  19. A. Dawar, D. Richerby and B. Rossman, Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs Annals of Pure and Applied Logic, 152 (2008), 31-50.
  20. A. Dawar and D. Richerby, The Power of Counting Logics on Restricted Classes of Finite Structures, CSL'07: Computer Science and Logic, Lecture Notes in Computer Science, Springer-Verlag (2007).
  21. A. Dawar and S. Kreutzer, Generalising Automaticity to Modal Properties of Finite Structures Theoretical Computer Science, 379 (2007), 266-285.
  22. A. Dawar and D. Janin, The Monadic Theory of Finite Representations of Infinite Words Information Processing Letters, 103 (2007) 94-101.
  23. A. Dawar, M. Grohe and S. Kreutzer, Locally Excluding a Minor, Proc. 22nd IEEE Symp. on Logic in Computer Science, IEEE Computer Society Press (2007).
  24. A. Dawar, M. Grohe, S. Kreutzer and N. Schweikardt, Model Theory Makes Formulas Large Proc. 34th International Colloquium on Automata, Languages and Programming - ICALP'07, Lecture Notes in Computer Science vol. 4596, Springer-Verlag (2007) 913-924. A longer version is available as preprint NI07003-LAA, Isaac Newton Institute of Mathematical Sciences (2007).
  25. A. Dawar, P. Gardner and G. Ghelli, Expressiveness and Complexity of Graph Logic, Information and Computation, 205 (2007) 263-310.
  26. A. Dawar, S. Kreutzer, M. Grohe and N. Schweikardt, Approximation Schemes for First-Order Definable Optimisation Problems Proc. 21st IEEE Symp. on Logic in Computer Science, IEEE Computer Society Press (2006) 411-420.
  27. A. Atserias, A. Dawar and Ph.G. Kolaitis, On Preservation under Homomorphisms and Unions of Conjunctive Queries, Journal of the ACM, 53 (2006) 208-237.
  28. A. Dawar, E. Grädel and S. Kreutzer, Backtracking Games and Inflationary Fixed Points Theoretical Computer Science, 350 (2006) 174-187.
  29. D. Berwanger, A. Dawar, S. Kreutzer and P. Hunter DAG-Width and Parity Games Proc. 23rd International Symposium on Theoretical Aspects of Computer Science (STACS 2006), Lecture Notes in Computer Science, Springer-Verlag (2006).
  30. A. Dawar How Many First-Order Variables are Needed on Finite Ordered Structures? in We Will Show Them: Essays in Honour of Dov Gabbay, Vol 1., S. Artemov, H. Barringer, A. S. d'Avila Garcez, L. C. Lamb, and J. Woods (eds.), College Publications (2005).
  31. P. Hunter and A. Dawar Complexity Bounds for Regular Games Proc. 30th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Springer-Verlag (2005).
  32. A. Dawar, P. Gardner and G. Ghelli, Adjunct Elimination Through Games in Static Ambient Logic, Proc. 24th Conf. on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science vol. 3328, Springer-Verlag (2004).
  33. A. Dawar and D. Janin, On the Bisimulation Invariant Fragment of Monadic &Sigma1 in the Finite, Proc. 24th Conf. on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science vol. 3328, Springer-Verlag (2004).
  34. A. Dawar, E. Grädel and S. Kreutzer, Inflationary Fixed Points in Modal Logic, ACM Transactions on Computational Logic, 5(2) (2004), 282-315.
  35. A. Dawar and D. Richerby, A Fixed-Point Logic with Symmetric Choice, Computer Science Logic'03 (M. Baaz and J.A. Makowsky, eds), Lecture Notes in Computer Science vol. 2803, Springer-Verlag (2003), 169-182.
  36. A. Dawar and D. Richerby, Fixed-Point Logics with Nondeterministic Choice, Journal of Logic and Computation, 13(4) (2003), 503-530.
  37. A. Dawar and Y. Gurevich, Fixed Point Logics, Bulletin of Symbolic Logic, 8 (2002), 65-88.
  38. A. Dawar, Finite Models and Finitely Many Variables, Logic, Algebra and Computer Science (D. Niwinski and R. Maron, eds.), Banach Centre Publications vol. 46, Institute of Mathematics, Polish Academy of Sciences, (1999).
  39. A. Dawar, L. Hella and A. Seth, Ordering Finite Variable Types with Generalized Quantifiers, Proc. 13th IEEE Symp. on Logic in Computer Science, IEEE Computer Society Press (1998) 28-43.
  40. A. Dawar, A Restricted Second-Order Logic for Finite Structures, Information and Computation, 143 (1998) 154-174.
  41. A. Dawar, Types and Indiscernibles in Finite Models, Logic Colloquium '95 (J.A. Makowsky and E.V. Ravve, eds.) Lecture Notes in Logic vol. 11, Springer-Verlag (1998) 51-65.
  42. A. Dawar, G. Gottlob and L. Hella, Capturing Relativized Complexity Classes without Order, Mathematical Logic Quarterly, 44 (1998), 109-122.
  43. A. Dawar, K. Doets, S. Lindell and S. Weinstein, Elementary Properties of the Finite Ranks, Mathematical Logic Quarterly, 44 (1998) 349-353.
  44. A. Dawar, S. Lindell and S. Weinstein, First order logic, fixed point logic and linear order, Computer Science Logic '95, (H. Kleine Büning, ed.) Lecture Notes in Computer Science vol. 1092, Springer-Verlag (1996), 161-177.
  45. A. Dawar, L. Hella and Ph.G. Kolaitis, Implicit definability and infinitary logic in finite model theory, Proc. 22nd International Colloquium on Automata, Languages and Programming - ICALP 95, Lecture Notes in Computer Science vol. 944, Springer-Verlag (1995) 624-635.
  46. A. Dawar and L. Hella, The expressive power of finitely many generalized quantifiers, Information and Computation 123 (1995) 172-184.
  47. A. Dawar, S. Lindell and S. Weinstein, Infinitary logic and inductive definability over finite structures, Information and Computation 119 (1995) 160-175.
  48. A. Dawar, Generalized quantifiers and logical reducibilities, Journal of Logic and Computation 5 (1995) 213-226.
  49. A. Dawar and K. Vijay-Shanker, An Interpretation of Negation in Feature Structure Descriptions, Computational Linguistics, 16(1), (1990), 11-21.