Selected Publications
- A. Atserias and A. Dawar.
Definable
Inapproximability: New Challenges for Duplicator
CSL (2018).
- A. Dawar and G. Wilsenach.
Symmetric Circuits for Rank Logic
CSL (2018).
- S. Abramsky, A. Dawar, P. Wang.
The Pebbling Comonad in
Finite Model Theory, LiCS (2017).
- A. Dawar, P. Wang.
Definability
of semidefinite programming and Lasserre lower bounds for CSPs, LiCS
(2017).
- A. Dawar, B. Holm. Pebble Games with Algebraic Rules, Fundamenta Informaticae, 150 281-316 (2017).
- M. Anderson, A. Dawar.
On
Symmetric Circuits and Fixed-Point Logics, Theory of
Computing Systems,60 521-551 (2017).
- J. Bulian, A. Dawar.
Fixed-parameter Tractable Distances to Sparse Graph Classes.
Algorithmica> 79 139-158 (2017).
- J. Bulian, A. Dawar.
Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree,
Algorithmica 75 363-382 (2016).
- M. Anderson, A. Dawar,
B. Holm. Solving Linear
Programs without Breaking Abstractions. Journal of the ACM, 62 (2015).
- A. Atserias, A. Dawar.
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers,
ACM Transactions on Computational Logic, 15(1):6 (2014).
- 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).
- 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.
- 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.
-
A. Dawar,
Homomorphism Preservation on Quasi-Wide Classes,
Journal of Computer and System Sciences,
76 (2010), 324-332.
- A. Dawar and E. Grädel
Properties of Almost All Graphs and Generalized Quantifiers,
Fundamenta Informaticae,
98 (2010), 351-372.
-
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).
- A. Dawar and M. Otto,
Modal Characterisation Theorems over Special Classes of Frames
Annals of Pure and Applied Logic,
161 (2009), 1-42.
- 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.
- 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).
- A. Atserias, A. Bulatov and A. Dawar
Affine Systems of Equations and Counting Infinitary Logic,
Theoretical Computer Science 410 (2009), 1666-1683.
- 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.
- A. Atserias, A. Dawar and M. Grohe,
Preservation under Extensions on Well-behaved Finite Structures
SIAM J. on Computing,
38 (2008), 1364-1381.
- 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.
- 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.
- 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.
- 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).
- A. Dawar and S. Kreutzer,
Generalising Automaticity to Modal
Properties of Finite Structures
Theoretical Computer Science, 379 (2007), 266-285.
- A. Dawar and D. Janin,
The Monadic Theory of Finite Representations of Infinite Words
Information Processing Letters,
103 (2007) 94-101.
- 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).
- 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).
- A. Dawar, P. Gardner and G. Ghelli,
Expressiveness and Complexity of Graph
Logic, Information
and Computation, 205 (2007) 263-310.
- 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.
- 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.
- A. Dawar, E. Grädel and S. Kreutzer,
Backtracking Games and Inflationary Fixed
Points
Theoretical Computer Science, 350 (2006) 174-187.
- 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).
- 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).
- 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).
- 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).
- 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).
- A. Dawar, E. Grädel and S. Kreutzer,
Inflationary Fixed Points in Modal Logic,
ACM Transactions on Computational Logic, 5(2) (2004), 282-315.
- 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.
- A. Dawar and D. Richerby, Fixed-Point
Logics with Nondeterministic Choice, Journal of Logic and
Computation, 13(4) (2003), 503-530.
- A. Dawar and Y. Gurevich, Fixed Point Logics, Bulletin of Symbolic Logic, 8 (2002), 65-88.
- 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).
- 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.
- A. Dawar, A Restricted Second-Order Logic for Finite Structures, Information
and Computation, 143 (1998) 154-174.
- 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.
- A. Dawar, G. Gottlob and L. Hella, Capturing Relativized Complexity Classes
without Order, Mathematical Logic Quarterly, 44 (1998), 109-122.
- A. Dawar, K. Doets, S. Lindell and S. Weinstein, Elementary Properties
of the Finite Ranks, Mathematical Logic Quarterly, 44 (1998)
349-353.
- 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.
- 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.
- A. Dawar and L. Hella, The expressive power of finitely many generalized
quantifiers, Information and Computation 123 (1995) 172-184.
- A. Dawar, S. Lindell and S. Weinstein, Infinitary logic and inductive definability
over finite structures, Information and Computation 119 (1995)
160-175.
- A. Dawar, Generalized quantifiers and logical reducibilities, Journal
of Logic and Computation 5 (1995) 213-226.
- A. Dawar and K. Vijay-Shanker, An Interpretation of Negation in
Feature Structure Descriptions, Computational Linguistics,
16(1), (1990), 11-21.
- © 2018 Computer Laboratory, University of Cambridge