Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems
verfasst von : Yoshiharu Kojima, Masahiko Sakai
Erschienen in: Rewriting Techniques and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A reachability problem is a problem used to decide whether s is reachable to
t
by
R
or not for a given two terms
s
,
t
and a term rewriting system
R
. Since it is known that this problem is undecidable, effort has been devoted to finding subclasses of term rewriting systems in which the reachability is decidable. However few works on decidability exist for innermost reduction strategy or context-sensitive rewriting.
In this paper, we show that innermost reachability and contextsensitive reachability are decidable for linear right-shallow term rewriting systems. Our approach is based on the tree automata technique that is commonly used for analysis of reachability and its related properties.