Dieter Hofbauer

dblp:h/DieterHofbauer · DBLP profile ↗
← Back
20ranked-venue papers
12as first author
1since 2021 · last 2026
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 18 · 12 first-author · 1 since 2021Artificial intelligence and machine learning · 1Databases, data management, data science and information retrieval · 1 · 1 first-authorApplied, interdisciplinary, general and emerging computing · 1
YearPublicationVenuePosition
2026 New and Formalized Proofs for Right-Forward Closures and Core Matrix Interpretations
abstract
We provide new proofs of two important theorems for proving termination of term rewrite systems (TRSs), including a full formalization in Isabelle/HOL. We first consider Dershowitz' theorem that termination starting from arbitrary terms is equivalent to termination starting from terms in the right-forward closures of right-hand sides, provided that the TRS is right-linear or orthogonal. Our new proof deviates from the original one in that no reorderings of steps in infinite derivations are required, making it more precise in its argumentation. It also subsumes a later result that one can weaken orthogonality to locally confluent overlay TRSs. The second theorem is about matrix interpretations. These were introduced by Hofbauer and Waldmann for proving termination of string rewrite systems (SRSs), internally using the concept of a core. Subsequently, Endrullis, Waldmann and Zantema developed matrix interpretations for TRSs without using the idea of a core. Whereas matrix interpretations for TRSs have already been formalized several times, so far this was not the case for core SRS matrix interpretations. We not only provide such a formalization, but also extend core SRS matrix interpretations to TRSs. These new core matrix interpretations for TRSs generalize previous approaches.
René Thiemann, Dieter Hofbauer, Ulysse Le Huitouze, Johannes Waldmann
FSCD2
2010 Finding and Certifying Loops
Harald Zankl, Christian Sternagel, Dieter Hofbauer, Aart Middeldorp
SOFSEM3
2007 On tree automata that certify termination of left-linear term rewriting systems
Alfons Geser, Dieter Hofbauer, Johannes Waldmann, Hans Zantema
Inf. Comput.2
2006 Termination of String Rewriting with Matrix Interpretations
Dieter Hofbauer, Johannes Waldmann
RTA1
2006 Termination of {aa->bc, bb->ac, cc->ab}
Dieter Hofbauer, Johannes Waldmann
Inf. Process. Lett.1
2005 On Tree Automata that Certify Termination of Left-Linear Term Rewriting Systems
Alfons Geser, Dieter Hofbauer, Johannes Waldmann, Hans Zantema
RTA2
2005 Termination Proofs for String Rewriting Systems via Inverse Match-Bounds
Alfons Geser, Dieter Hofbauer, Johannes Waldmann
J. Autom. Reason.2
2005 On state-alternating context-free grammars
Etsuro Moriya, Dieter Hofbauer, Maria Huber, Friedrich Otto
Theor. Comput. Sci.2
2004 Finding Finite Automata That Certify Termination of String Rewriting
Alfons Geser, Dieter Hofbauer, Johannes Waldmann, Hans Zantema
CIAA2
2004 Deleting string rewriting systems preserve regularity
Dieter Hofbauer, Johannes Waldmann
Theor. Comput. Sci.1
2003 Deleting String Rewriting Systems Preserve Regularity
Dieter Hofbauer, Johannes Waldmann
Developments in Language Theory1
2003 Match-Bounded String Rewriting Systems
Alfons Geser, Dieter Hofbauer, Johannes Waldmann
MFCS2
2003 An upper bound on the derivational complexity of Knuth-Bendix orderings
Dieter Hofbauer
Inf. Comput.1
2002 Test Sets for the Universal and Existential Closure of Regular Tree Languages
Dieter Hofbauer, Maria Huber
Inf. Comput.1
2001 Termination Proofs by Context-Dependent Interpretations
Dieter Hofbauer
RTA1
1999 Test Sets for the Universal and Existential Closure of Regular Tree Languages
Dieter Hofbauer, Maria Huber
RTA1
1994 Linearizing Term Rewriting Systems Using Test Sets
Dieter Hofbauer, Maria Huber
J. Symb. Comput.1
1992 Termination Proofs by Multiset Path Orderings Imply Primitive Recursive Derivation Lengths
Dieter Hofbauer
Theor. Comput. Sci.1
1991 Time Bounded Rewrite Systems and Termination Proofs by Generalized Embedding
Dieter Hofbauer
RTA1
1989 Termination Proofs and the Length of Derivations (Preliminary Version)
Dieter Hofbauer, Clemens Lautemann
RTA1