In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating (or strongly normalizing) abstract rewriting system (ARS), that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent. In fact a terminating ARS is confluent precisely when it is locally confluent. Today, this is seen as a purely combinatorial result based on well-foundedness due to a proof of Gérard Huet in 1980. Newman's original proof was considerably more complicated.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Diamond Lemma (de)
- Lemme de Newman (fr)
- Newman's lemma (en)
- Lema de Newman (pt)
|
| rdfs:comment
| - In der theoretischen Informatik besagt das Diamond Lemma (auch: der Satz von Newman, nach Max Newman), dass eine Relation genau dann konfluent ist, wenn sie ist. Dieses Resultat ist die Grundlage zur Entscheidbarkeit der Konfluenz bei terminierenden Termersetzungssystemen. Da das Diagramm im Beweis dieses Satzes entfernt an einen Diamanten erinnert, hat er diesen Namen bekommen. (de)
- En mathématiques et en informatique, plus précisément dans la théorie des relations binaires, le lemme de Newman dit qu'une relation binaire noethérienne est confluente si elle est localement confluente. Une démonstration relativement simple (induction sur une relation bien fondée) est due à Gérard Huet en 1980. La démonstration originale de Newman est plus compliquée, mais la méthode des diagrammes décroissants[Quoi ?] montre bien comment elle fonctionne. (fr)
- In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating (or strongly normalizing) abstract rewriting system (ARS), that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent. In fact a terminating ARS is confluent precisely when it is locally confluent. Today, this is seen as a purely combinatorial result based on well-foundedness due to a proof of Gérard Huet in 1980. Newman's original proof was considerably more complicated. (en)
- Na teoria dos sistemas de reescrita, o lema de Newman enuncia que um sistema de redução abstrato noetheriano (ou fortemente normalizante, isto é, um sistena no qual não há cadeias de redução infinitas) é confluente se, e somente se, ele for localmente confluente. Esta propriedade dos sistemas de redução abstratos pode ser utilizada para mostrar a confluência de tais sistemas. (pt)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| date
| |
| title
| |
| url
| |
| urlname
| |
| has abstract
| - In der theoretischen Informatik besagt das Diamond Lemma (auch: der Satz von Newman, nach Max Newman), dass eine Relation genau dann konfluent ist, wenn sie ist. Dieses Resultat ist die Grundlage zur Entscheidbarkeit der Konfluenz bei terminierenden Termersetzungssystemen. Da das Diagramm im Beweis dieses Satzes entfernt an einen Diamanten erinnert, hat er diesen Namen bekommen. (de)
- En mathématiques et en informatique, plus précisément dans la théorie des relations binaires, le lemme de Newman dit qu'une relation binaire noethérienne est confluente si elle est localement confluente. Une démonstration relativement simple (induction sur une relation bien fondée) est due à Gérard Huet en 1980. La démonstration originale de Newman est plus compliquée, mais la méthode des diagrammes décroissants[Quoi ?] montre bien comment elle fonctionne. (fr)
- In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating (or strongly normalizing) abstract rewriting system (ARS), that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent. In fact a terminating ARS is confluent precisely when it is locally confluent. Equivalently, for every binary relation with no decreasing infinite chains and satisfying a weak version of the diamond property, there is a unique minimal element in every connected component of the relation considered as a graph. Today, this is seen as a purely combinatorial result based on well-foundedness due to a proof of Gérard Huet in 1980. Newman's original proof was considerably more complicated. (en)
- Na teoria dos sistemas de reescrita, o lema de Newman enuncia que um sistema de redução abstrato noetheriano (ou fortemente normalizante, isto é, um sistena no qual não há cadeias de redução infinitas) é confluente se, e somente se, ele for localmente confluente. Esta propriedade dos sistemas de redução abstratos pode ser utilizada para mostrar a confluência de tais sistemas. Atualmente o lema é visto como sendo um resultado puramente combinatorial baseado em uma propriedade válida para algumas relações (de serem bem-fundadas), devido a uma prova por indução noetheriana dada por em 1980. A demonstração original de Newman foi consideravelmente mais complicada. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is known for
of | |
| is known for
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
