About: Orthogonality (term rewriting)

An Entity of Type: System104377057, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Orthogonality as a property of term rewriting systems (TRSs) describes where the reduction rules of the system are all left-linear, that is each variable occurs only once on the left hand side of each reduction rule, and there is no overlap between them, i.e. the TRS has no critical pairs. For example is not left-linear. Orthogonal TRSs have the consequent property that all reducible expressions (redexes) within a term are completely disjoint -- that is, the redexes share no common function symbol. For example, the TRS with reduction rules Orthogonal TRSs are confluent.

Property Value
dbo:abstract
  • Orthogonality as a property of term rewriting systems (TRSs) describes where the reduction rules of the system are all left-linear, that is each variable occurs only once on the left hand side of each reduction rule, and there is no overlap between them, i.e. the TRS has no critical pairs. For example is not left-linear. Orthogonal TRSs have the consequent property that all reducible expressions (redexes) within a term are completely disjoint -- that is, the redexes share no common function symbol. For example, the TRS with reduction rules is orthogonal -- it is easy to observe that each reduction rule is left-linear, and the left hand side of each reduction rule shares no function symbol in common, so there is no overlap. Orthogonal TRSs are confluent. (en)
dbo:wikiPageID
  • 5099917 (xsd:integer)
dbo:wikiPageLength
  • 2356 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1043351555 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdf:type
rdfs:comment
  • Orthogonality as a property of term rewriting systems (TRSs) describes where the reduction rules of the system are all left-linear, that is each variable occurs only once on the left hand side of each reduction rule, and there is no overlap between them, i.e. the TRS has no critical pairs. For example is not left-linear. Orthogonal TRSs have the consequent property that all reducible expressions (redexes) within a term are completely disjoint -- that is, the redexes share no common function symbol. For example, the TRS with reduction rules Orthogonal TRSs are confluent. (en)
rdfs:label
  • Orthogonality (term rewriting) (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License