49 citations · 106 across the 25 of their papers we have counts for
36 papers
Finding Common Mistakes In Modelling With Mathematical Formalisms Using LLMs
Lilian Killich, Marko Schmellenkamp, Fabian Vehlken +1
Modelling with mathematical formalisms like logical formulas, mathematical equations, or regular expressions is an important yet challenging task for students of computer science a…
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…
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…
Difficulty Generating Factors for Context-free Language Construction Assignments
Florian Schmalstieg, Marko Schmellenkamp, Jakob Schwerter +1
Computer science students often struggle with abstract theoretical concepts, particularly in introductory courses on theoretical computer science. One such challenge is understandi…
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…
Learning Tree Pattern Transformations
Daniel Neider, Leif Sabellek, Johannes Schmidt +2
Explaining why and how a tree structurally differs from another tree is a question that is encountered throughout computer science, including in understanding tree-st…
Exploring Error Types in Formal Languages Among Students of Upper Secondary Education
Marko Schmellenkamp, Dennis Stanglmair, Tilman Michaeli +1
Foundations of formal languages, as subfield of theoretical computer science, are part of typical upper secondary education curricula. There is very little research on the potentia…
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…
Specification and Automatic Verification of Computational Reductions
Julien Grange, Fabian Vehlken, Nils Vortmeier +1
We are interested in the following validation problem for computational reductions: for algorithmic problems and , is a given candidate reduction indeed a reduction fr…
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…
Tool-Assisted Learning of Computational Reductions
Tristan Kneisel, Elias Radtke, Marko Schmellenkamp +2
Computational reductions are an important and powerful concept in computer science. However, they are difficult for many students to grasp. In this paper, we outline a concept for…
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…
Iltis: Learning Logic in the Web
Gaetano Geck, Christine Quenkert, Marko Schmellenkamp +4
The Iltis project provides an interactive, web-based system for teaching the foundations of formal methods. It is designed with the objective to allow for simple inclusion of new e…
Work-sensitive Dynamic Complexity of Formal Languages
Jonas Schmidt, Thomas Schwentick, Till Tantau +2
Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering member…
Register Automata with Extrema Constraints, and an Application to Two-Variable Logic
Szymon Toruńczyk, Thomas Zeume
We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can…
Dynamic complexity of Reachability: How many changes can we handle?
Samir Datta, Pankaj Kumar, Anish Mukherjee +3
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was exte…
Dynamic Complexity Meets Parameterised Algorithms
Jonas Schmidt, Thomas Schwentick, Nils Vortmeier +2
Dynamic Complexity studies the maintainability of queries with logical formulas in a setting where the underlying structure or database changes over time. Most often, these formula…
Dynamic Complexity of Parity Exists Queries
Nils Vortmeier, Thomas Zeume
Given a graph whose nodes may be coloured red, the parity of the number of red nodes can easily be maintained with first-order update rules in the dynamic complexity framework DynF…
A More General Theory of Static Approximations for Conjunctive Queries
Pablo Barceló, Miguel Romero, Thomas Zeume
Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. Approximating a hard CQ by a query from such a fragment can thus al…
Reachability and Distances under Multiple Changes
Samir Datta, Anish Mukherjee, Nils Vortmeier +1
Recently it was shown that the transitive closure of a directed graph can be updated using first-order formulas after insertions and deletions of single edges in the dynamic descri…
Introduction to Iltis: An Interactive, Web-Based System for Teaching Logic
Gaetano Geck, Artur Ljulin, Sebastian Peter +3
Logic is a foundation for many modern areas of computer science. In artificial intelligence, as a basis of database query languages, as well as in formal software and hardware veri…