Nonterminating rewritings with head boundedness

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We define here the concept of head boundedness, head normal form and head confluence of term rewriting systems that allow infinite derivations. Head confluence is weaker than confluence, but sufficient to guarantee the correctness of lazy implementations of equational logic programming languages. Then we prove several results. First, if a left-linear system is locally confluent and head-bounded, then it is head-confluent. Second, head-confluent and head-bounded systems have the head Church-Rosser property. Last, if an orthogonal system is head-terminating, then it is head-bounded. These results can be applied to generalize equational logic programming languages.

Original languageEnglish
Pages (from-to)162-171
Number of pages10
JournalJournal of Computer Science and Technology
Volume8
Issue number2
DOIs
StatePublished - Apr 1993
Externally publishedYes

Keywords

  • Term rewriting system
  • confluence
  • termination

Fingerprint

Dive into the research topics of 'Nonterminating rewritings with head boundedness'. Together they form a unique fingerprint.

Cite this