Sémidoc 17 mars 2011

Marc Sylvestre (LaBRI)


17 mars 2011
Bounded rewriting for words and terms.
We study a rewriting strategy called the bounded stategy. First, we introduce this stategy for semi-Thue rewriting systems and linear term rewriting systems and we show that several termination problems are decidable for this stategy. Then, we extend it to left-linear term rewriting systems, and we show that bounded rewriting effectively inverse-preserves recognizability.