Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems

Autor:	Yoshiharu Kojima, Masahiko Sakai
Rok vydání:	2008
Předmět:	Discrete mathematics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Reachability Reachability problem TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Confluence Context (language use) Rewriting Term (logic) Undecidable problem Mathematics Decidability
Zdroj:	Rewriting Techniques and Applications ISBN: 9783540705888 RTA
DOI:	10.1007/978-3-540-70590-1_13
Popis:	A reachability problem is a problem used to decide whether s is reachable to tby Ror not for a given two terms s, tand 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::33c2a66cf1aab50efb870cc09d9007f1 https://doi.org/10.1007/978-3-540-70590-1_13 Zobrazit plný text záznamu