Reachability and confluence are undecidable for flat term rewriting systems

Florent Jacquemard 1
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : Ground reachability, ground joinability and confluence are shown undecidable for flat term rewriting systems, i.e. systems in which all left and right members of rule have depth at most one.
Document type :
Journal articles
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00578875
Contributor : Florent Jacquemard <>
Submitted on : Tuesday, March 22, 2011 - 3:26:51 PM
Last modification on : Thursday, February 7, 2019 - 5:29:23 PM
Long-term archiving on : Thursday, June 23, 2011 - 2:47:55 AM

File

jacquemard-IPL-HAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00578875, version 1

Collections

Citation

Florent Jacquemard. Reachability and confluence are undecidable for flat term rewriting systems. Information Processing Letters, Elsevier, 2003, 87 (5), pp.265-270. ⟨inria-00578875⟩

Share

Metrics

Record views

189

Files downloads

211