9 papers
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…
Cross-Course Generalizability of SRL-Aligned Predictive Models Using Digital Learning Traces
Jakob Schwerter, Loreen Sabel, Judith Bose +5
STEM dropout rates remain high at universities, particularly in computer science programs with theory-intensive courses. Digital learning environments now capture rich behavioral d…
Detecting and Explaining (In-)equivalence of Context-Free Grammars
Marko Schmellenkamp, Thomas Zeume, Sven Argo +3
We propose a scalable framework for deciding, proving, and explaining (in-)equivalence of context-free grammars. We present an implementation of the framework and evaluate it on la…
NILE: Formalizing Natural-Language Descriptions of Formal Languages
Tristan Kneisel, Marko Schmellenkamp, Fabian Vehlken +1
This paper explores how natural-language descriptions of formal languages can be compared to their formal representations and how semantic differences can be explained. This is mot…
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…