FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Semantic Kachinuki Order

Authors: Alfons Geser, Dieter Hofbauer and Johannes Waldmann

Paper Information

Title:Semantic Kachinuki Order
Authors:Alfons Geser, Dieter Hofbauer and Johannes Waldmann
Proceedings:WST WST2018proceedings
Editor: Salvador Lucas
Keywords:termination, string rewriting, Kachinuki order
Abstract:

ABSTRACT. We present an extension of the Kachinuki order on strings. The Kachinuki order transforms the problem of comparing strings to the problem of comparing their syllables length-lexicographically, where the syllables are defined via a precedence on the alphabet. Our extension allows the number of syllables to increase under rewriting, provided we bound it by a weakly compatible interpretation.

Pages:1
Talk:Jul 18 14:00 (Session 127Q: Program termination and orderings (II))
Paper: