Publications
Showing 1 - 50 of 125 Results
-
SourceAuthor(s)
-
[Contribution to a book, Contribution to a conference proceedings]
New Optimizations and Heuristics for Determinization of Büchi Automata
In: Automated Technology for Verification and Analysis : 17th International Symposium, ATVA 2019, Taipei, Taiwan, October 28-31, 2019, Proceedings / Yu-Fang Chen, Chih-Hong Cheng, Javier Esparza (eds.), 317-333, 2019
[DOI: 10.1007/978-3-030-31784-3_18]Löding, Christof
Pirogov, Anton -
[Contribution to a book, Contribution to a conference proceedings]
Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks
In: The Thirty-Third AAAI Conference on Artificial Intelligence, the Thirty-First Innovative Applications of Artificial Intelligence Conference, the Ninth AAAI Symposium on Educational Advances in Artificial Intelligence : Honolulu, Hawaii USA - January 27-February 1, 2019 / sponsored by the Association for the Advancement of Artificial Intelligence, 4602-4609, 2019
[DOI: 10.1609/aaai.v33i01.33014602]Morris, Christopher
Ritzert, Martin Alexander Felix
Fey, Matthias
Hamilton, William L.
Lenssen, Jan Eric
et al. -
[Contribution to a book, Contribution to a conference proceedings]
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
In: 44th International Symposium on Mathematical Foundations of Computer Science : MFCS 2019, August 26-30, 2019, Aachen, Germany / edited by Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen, 45:1-45:15, 2019
[DOI: 10.4230/LIPICS.MFCS.2019.45]Kiefer, Sandra
Neuen, Daniel -
[Preprint]
Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words, 32 Seiten, 2019Löding, Christof
Spinrath, Christopher -
[Journal Article]
Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
In: Discrete mathematics and theoretical computer science : DMTCS, 21 (3), 4, 2019Löding, Christof
Spinrath, Christopher -
[Contribution to a book, Contribution to a conference proceedings]
Tangles and Single Linkage Hierarchical Clustering
In: 44th International Symposium on Mathematical Foundations of Computer Science : MFCS 2019, August 26-30, 2019, Aachen, Germany / edited by Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen, 38:1-38:12, 2019
[DOI: 10.4230/LIPICS.MFCS.2019.38]Fluck, Eva -
[Contribution to a book, Contribution to a conference proceedings]
Learning Concepts Definable in First-Order Logic with Counting
In: 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) : [Proceedings], 2019
[DOI: 10.1109/LICS.2019.8785811]van Bergerem, Steffen -
[Contribution to a conference proceedings]
String-to-String Interpretations With Polynomial-Size Output
In: [46th International Colloquium on Automata, Languages and Programming], 2019
[DOI: 10.4230/LIPICS.ICALP.2019.106]Bojanczyk, Mikolaj
Kiefer, Sandra
Lhote, Nathan -
[Contribution to a conference proceedings]
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
In: [46th International Colloquium on Automata, Languages and Programming, ICALP], 2019
[DOI: 10.4230/LIPICS.ICALP.2019.117]Grohe, Martin
Kiefer, Sandra -
[Journal Article]
Upper bounds on the quantifier depth for graph differentiation in first-order logic
In: Logical methods in computer science, 15 (2), 1-15, 2019
[DOI: 10.23638/LMCS-15(2:19)2019]Kiefer, Sandra
Schweitzer, Pascal -
[Contribution to a book, Contribution to a conference proceedings]
Probabilistic Databases with an Infinite Open-World Assumption
In: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 17-31, 2019
[DOI: 10.1145/3294052.3319681]Grohe, Martin
Lindner, Peter -
[Contribution to a conference proceedings]
Determinization of Büchi Automata: Unifying the Approaches of Safra and Muller-Schupp
In: [46th International Colloquium on Automata, Languages and Programming, ICALP 2019, 2019-07-08 - 2019-07-12, Patras, Greece], 2019
[DOI: 10.4230/LIPIcs.ICALP.2019.120]Löding, Christof
Pirogov, Anton -
[Journal Article]
A Finite-Model-Theoretic View on Propositional Proof Complexity
In: Logical methods in computer science, 15 (1), pp. 4:1-4:53, 2019
[DOI: 10.23638/LMCS-15(1:4)2019]Grädel, Erich
Grohe, Martin
Pago, Benedikt
Pakusa, Wied -
[Contribution to a book, Contribution to a conference proceedings]
Flat Model Checking for Counting LTL Using Quantifier-Free Presburger Arithmetic
In: Verification, Model Checking, and Abstract Interpretation : 20th International Conference, VMCAI 2019, Cascais, Portugal, January 13-15, 2019, Proceedings / edited by Constantin Enea, Ruzica Piskac, 513-534, 2019
[DOI: 10.1007/978-3-030-11245-5_24]Decker, Normann
Pirogov, Anton -
[Journal Article]
Characterising bounded expansion by neighbourhood complexity
In: European journal of combinatorics, 75, 152-168, 2018
[DOI: 10.1016/j.ejc.2018.08.001]Reidl, Felix
Sanchez Villaamil, Fernando
Stavropoulos, Konstantinos -
[Dissertation / PhD Thesis]
Synthesis of transducers from relations on finite words and trees, 1 Online-Ressource (viii, 182 Seiten) : Illustrationen, 2018Winter, Sarah -
[Journal Article]
Coloring and Covering Nowhere Dense Graphs
In: SIAM Journal on Discrete Mathematics, 32 (4), 2467-2481, 2018
[DOI: 10.1137/18M1168753]Grohe, Martin
Kreutzer, Stephan
Rabinovich, Roman
Siebertz, Sebastian
Stavropoulos, Konstantinos -
[Contribution to a book, Contribution to a conference proceedings]
First-Order Query Evaluation with Cardinality Conditions
In: PODS'18 : Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, June 10-15, 2018, Houston, TX, USA / General Chair: Jan Van den Bussche, 253-266, 2018
[DOI: 10.1145/3196959.3196970]Grohe, Martin
Schweikardt, Nicole -
[Contribution to a book, Contribution to a conference proceedings]
Graph Similarity and Approximate Isomorphism
In: 43rd International Symposium on Mathematical Foundations of Computer Science : MFCS 2018, August 27-31, 2018, Liverpool, United Kingdom / edited by Igor Potapov, Paul Spirakis, James Worrell, 20, [1]-16, 2018
[DOI: 10.4230/LIPIcs.MFCS.2018.20]Grohe, Martin
Rattan, Gaurav
Wöginger, Gerhard Johannes -
[Contribution to a book, Contribution to a conference proceedings]
An Improved Isomorphism Test for Bounded-Tree-Width Graphs
In: 45th International Colloquium on Automata, Languages, and Programming : ICALP 2018, Prague, Czech Republic, July 9-13, 2018 / edited by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald Sannella ; European Association for Theoretical Computer Science (EATCS), 67, [1]-14, 2018
[DOI: 10.4230/LIPIcs.ICALP.2018.67]Grohe, Martin
Neuen, Daniel
Schweitzer, Pascal
Wiebking, Daniel -
[Contribution to a book, Contribution to a conference proceedings]
A Faster Isomorphism Test for Graphs of Small Degree
In: 59th Annual IEEE Symposium on Foundations of Computer Science : FOCS 2018 : 7-9 October 2018, Paris, France : proceedings / edited by: Mikkel Thorup ; publisher: IEEE, 89-100, 2018
[DOI: 10.1109/FOCS.2018.00018]Grohe, Martin
Neuen, Daniel
Schweitzer, Pascal -
[Contribution to a book, Contribution to a conference proceedings]
Lovász Meets Weisfeiler and Leman
In: 45th International Colloquium on Automata, Languages, and Programming : ICALP 2018, Prague, Czech Republic, July 9-13, 2018 / edited by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald Sannella ; European Association for Theoretical Computer Science (EATCS), 40, [1]-14, 2018
[DOI: 10.4230/LIPIcs.ICALP.2018.40]Dell, Holger
Grohe, Martin
Rattan, Gaurav -
[Contribution to a book, Contribution to a conference proceedings]
Definable decompositions for graphs of bounded linear cliquewidth
In: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) : Oxford, United Kingdom - July 09-12, 2018, 1-10, 2018
[DOI: 10.1145/3209108.3209135]Bojańczyk, Mikołaj
Grohe, Martin
Pilipczuk, Michał -
[Contribution to a book, Contribution to a conference proceedings]
An exponential lower bound for individualization-refinement algorithms for graph isomorphism
In: STOC'18 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing : June 25-29, 2018, Los Angeles, CA, USA / sponsored by: ACM SIGACT, 138-150, 2018
[DOI: 10.1145/3188745.3188900]Neuen, Daniel
Schweitzer, Pascal -
[Contribution to a book, Contribution to a conference proceedings]
Climbing up the Elementary Complexity Classes with Theories of Automatic Structures
In: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) / Herausgeber: Dan Ghica, Achim Jung, 3:1-3:16, 2018
[DOI: 10.4230/LIPIcs.CSL.2018.3]Abu Zaid, Faried
Kuske, Dietrich
Lindner, Peter -
[Journal Article]
On the complexity of noncommutative polynomial factorization
In: Information and computation, 262, 22-39, 2018
[DOI: 10.1016/j.ic.2018.05.009]Arvind, V.
Joglekar, Pushkar
Rattan, Gaurav -
[Contribution to a book, Contribution to a conference proceedings]
Uniformization Problems for Synchronizations of Automatic Relations on Words
In: 45th International Colloquium on Automata, Languages, and Programming : ICALP 2018, Prague, Czech Republic, July 9-13, 2018 / edited by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald Sannella ; European Association for Theoretical Computer Science (EATCS), 142, [1]-13, 2018
[DOI: 10.4230/LIPIcs.ICALP.2018.142]Winter, Sarah -
[Contribution to a book, Contribution to a conference proceedings]
On Finitely Ambiguous Büchi Automata
In: Developments in language theory ; 22nd international conference, DLT 2018, Tokyo, Japan, September 10-14, 2018 : proceedings / Mizuho Hoshi, Shinnosuke Seki (eds.), 503-515, 2018
[DOI: 10.1007/978-3-319-98654-8_41]Löding, Christof
Pirogov, Anton -
[Journal Article]
Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
In: ACM transactions on computational logic : TOCL, 19 (2), 7, 2018
[DOI: 10.1145/3154456]Pakusa, Wied
Schalthöfer, Svenja
Selman, Aziz Erkal -
[Journal Article]
Pure Strategies in Imperfect Information Stochastic Games
In: Fundamenta informaticae, 160 (4), 361-384, 2018
[DOI: 10.3233/FI-2018-1687]Carayol, Arnaud
Löding, Christof
Serre, Olivier -
[Contribution to a conference proceedings, Journal Article]
Finite Automata Over Infinite Alphabets : Two Models with Transitions for Local Change
In: International journal of foundations of computer science : IJFCS, 29 (2), 213-231, 2018
[DOI: 10.1142/S012905411840004X]Czyba, Christopher
Thomas, Wolfgang
Spinrath, Christopher -
[Journal Article, Review]
Bernhardt, Chris: Turing's Vision: The Birth of Computer Science. - London, 2016. - ISBN: 978-0-262-33380-1
In: Isis : electronic edition, 109 (1), 213-214, 2018Thomas, Wolfgang -
[Preprint]
A Finite-Model-Theoretic View on Propositional Proof Complexity, 53 Seiten, 2018Grädel, Erich
Grohe, Martin
Pago, Benedikt
Pakusa, Wied -
[Contribution to a conference proceedings, Journal Article]
Foundations for natural proofs and quantifier instantiation
In: Proceedings of the ACM on Programming Languages : PACMPL, 2, 10, 2018
[DOI: 10.1145/3158098]Löding, Christof
Madhusudan, P.
Peńa, Lucas -
[Preprint]
An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism, 21 Seiten, 2017Neuen, Daniel
Schweitzer, Pascal -
[Contribution to a book, Contribution to a conference proceedings]
The Weisfeiler-Leman dimension of planar graphs is at most 3
In: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) : 20-23 June 2017, Reykjavík, Iceland, 1-12, 2017
[DOI: 10.1109/LICS.2017.8005107]Kiefer, Sandra
Ponomarenko, Ilia
Schweitzer, Pascal -
[Contribution to a conference proceedings, Journal Article]
Synthesis of deterministic top-down tree transducers from automatic tree relations
In: Information and computation, 253 (Part 2), 336-354, 2016
[DOI: 10.1016/j.ic.2016.07.013]Löding, Christof
Winter, Sarah -
[Contribution to a book, Contribution to a conference proceedings]
Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
In: Fundamentals of computation theory : 21st international symposium, FCT 2017, Bordeaux, France, September 11-13, 2017 : proceedings / Ralf Klasing, Marc Zeitoun (eds.), 341-354, 2017
[DOI: 10.1007/978-3-662-55751-8_27]Löding, Christof
Spinrath, Christopher -
[Contribution to a book, Contribution to a conference proceedings]
N-Memory Automata over the Alphabet N
In: Language and automata theory and applications : 11th international conference, LATA 2017, Umeĺ, Sweden, March 6-9, 2017 : proceedings / Frank Drewes, Carlos Martín-Vide, Bianca Truthe (eds.), 91-102, 2017
[DOI: 10.1007/978-3-319-53733-7_6]Brütsch, Benedikt
Landwehr, Patrick
Thomas, Wolfgang -
[Preprint]
Benchmark Graphs for Practical Graph Isomorphism, 1-32, 2017Neuen, Daniel
Schweitzer, Pascal -
[Contribution to a book, Contribution to a conference proceedings]
Benchmark Graphs for Practical Graph Isomorphism
In: 25th European Symposium on Algorithms : ESA 2017, September 4-6, 2017, Vienna, Austria / edited by Kirk Pruhs, Christian Sohler, Seiten 60:1-60:14, 2017
[DOI: 10.4230/LIPIcs.ESA.2017.60]Neuen, Daniel
Schweitzer, Pascal -
[Contribution to a book, Contribution to a conference proceedings]
The Hardness of Embedding Grids and Walls
In: Graph-theoretic concepts in computer sciene : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017 : revised selected papers / Hans L. Bodlaender, Gerhard J. Woeginger (eds.), 180-192, 2017
[DOI: 10.1007/978-3-319-68705-6_14]Grohe, Martin
Chen, Yijia
Lin, Bingkai -
[Contribution to a book, Contribution to a conference proceedings]
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms / Society for Industrial and Applied Mathematics / Philip N. Klein (ed.), 327-339, 2017
[DOI: 10.1137/1.9781611974782.21]Berkholz, Christoph
Grohe, Martin -
[Contribution to a book, Contribution to a conference proceedings]
Learning first-order definable concepts over structures of small degree
In: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) : 20-23 June 2017, Reykjavík, Iceland, 1-12, 2017
[DOI: 10.1109/LICS.2017.8005080]Grohe, Martin
Ritzert, Martin Alexander Felix -
[Contribution to a book, Contribution to a conference proceedings]
Learning MSO-definable hypotheses on strings
In: [International Conference on Algorithmic Learning Theory, ALT 2017, 2017-10-15 - 2017-10-17, Kyoto, Japan], 434-451, 2017Grohe, Martin
Löding, Christof
Ritzert, Martin -
[Journal Article]
Canonizing Graphs of Bounded Tree Width in Logspace
In: ACM transactions on computation theory : TOCT, 9 (3), 12, 2017
[DOI: 10.1145/3132720]Elberfeld, Michael
Schweitzer, Pascal -
[Journal Article]
Minimal asymmetric graphs
In: Journal of combinatorial theory / B, 127, 215-227, 2017
[DOI: 10.1016/j.jctb.2017.06.003]Schweitzer, Pascal
Schweitzer, Patrick -
[Contribution to a book, Contribution to a conference proceedings, Journal Article]
Towards an Isomorphism Dichotomy for Hereditary Graph Classes
In: Theory of computing systems, 61 (4), 1084-1127, 2017
[DOI: 10.1007/s00224-017-9775-8]Schweitzer, Pascal -
[Journal Article]
Deciding First-Order Properties of Nowhere Dense Graphs
In: Journal of the ACM, 64 (3), 1-32, 2017
[DOI: 10.1145/3051095]Grohe, Martin
Kreutzer, Stephan
Siebertz, Sebastian -
[Contribution to a book, Contribution to a conference proceedings]
Descriptive Complexity of Linear Equation Systems and Applications to Propositional Proof Complexity
In: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) : 20-23 June 2017, Reykjavík, Iceland, 2017
[DOI: 10.1109/LICS.2017.8005081]Grohe, Martin
Pakusa, Wied