|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010104,
author = {Kai Salomaa},
title = {On the Modularity of Decidability of Completeness
and Termination},
journal = jalc,
year = 1996,
volume = 1,
number = 1,
pages = {37--53},
keywords = {term rewriting systems, modularity, decidability,
Post correspondence problem},
abstract = {We consider decision problems for direct sums of term
rewriting systems where the components belong to classes for
which the corresponding property is decidable. We show that
decidability of termination is not a modular property for
finite left-linear monadic term rewriting systems. It is
known that termination is not modular. Our result
generalizes this nonmodularity result by establishing that
for given two terminating finite left-linear term rewriting
systems we cannot even decide algorithmically whether or not
their direct sum terminates. Decidability of confluence and
decidability of completeness of (left- or right-) linear
term rewriting systems are shown to be modular. Decidability
of completeness of general systems is shown to be nonmodular.}
}