2 citations · 3 across the 12 of their papers we have counts for
12 papers · 1 filter
Dynamic Planar Graph Isomorphism is in DynFO
Samir Datta, Asif Khan, Felix Tschirbs +2
Consider two planar graphs which are subject to edge insertions and deletions. We show that whether the two graphs are isomorphic can be maintained with first-order logic formulas…
Identifying and Explaining (Non-)Equivalence of First-Order Logic Formulas
Fabian Vehlken, Thomas Zeume, Emilio Carrasco Bustamante +2
First-order logic is the basis for many knowledge representation formalisms and methods. Providing technological support for learning to write first-order formulas for natural lang…
Algebraic Characterizations of Classes of Regular Languages in DynFO
Corentin Barloy, Felix Tschirbs, Nils Vortmeier +1
This paper explores the fine-grained structure of classes of regular languages maintainable in fragments of first-order logic within the dynamic descriptive complexity framework of…
Logical Modelling in CS Education: Bridging the Natural Language Gap
Tristan Kneisel, Fabian Vehlken, Thomas Zeume
An important learning objective for computer science students is to learn how to formalize descriptions of real world scenarios in order to subsequently solve real world challenges…
Query maintenance under batch changes with small-depth circuits
Samir Datta, Asif Khan, Anish Mukherjee +3
Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaini…
The Regular Languages of First-Order Logic with One Alternation
Corentin Barloy, Michaël Cadilhac, Charles Paperman +1
The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary formula de…