The Confluence Problem for Flat TRSs

Ichiro Mitsuhashi 1 Michio Oyamaguch 1 Florent Jacquemard 2
2 DAHU - Verification in databases
CNRS - Centre National de la Recherche Scientifique : UMR8643, Inria Saclay - Ile de France, ENS Cachan - École normale supérieure - Cachan, LSV - Laboratoire Spécification et Vérification [Cachan]
Abstract : We prove that the properties of reachability, joinability and confluence are undecidable for flat TRSs. Here, a TRS is flat if the heights of the left and right-hand sides of each rewrite rule are at most one.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00579010
Contributor : Florent Jacquemard <>
Submitted on : Wednesday, March 23, 2011 - 10:29:45 AM
Last modification on : Tuesday, August 13, 2019 - 9:28:04 AM
Long-term archiving on : Friday, June 24, 2011 - 2:34:00 AM

File

MOJ-aisc06.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ichiro Mitsuhashi, Michio Oyamaguch, Florent Jacquemard. The Confluence Problem for Flat TRSs. 8th International Conference Artificial Intelligence and Symbolic Computation (AISC), Sep 2006, Beijing, China. pp.68-81, ⟨10.1007/11856290_8⟩. ⟨inria-00579010⟩

Share

Metrics

Record views

237

Files downloads

235