This HTML5 document contains 133 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n18https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n20https://books.google.com/
n19https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
n16http://cl-informatik.uibk.ac.at/software/kbcv/
n22https://hal.inria.fr/inria-00076536/file/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:Bendix
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageDisambiguates
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Encompassment_ordering
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Path_ordering_(term_rewriting)
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Vampire_(theorem_prover)
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Rewriting
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Timeline_of_algorithms
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Computer_algebra_system
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Sridhar_Tayur
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Superposition_calculus
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Buchberger's_algorithm
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:RE_(complexity)
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Word_problem_for_groups
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Donald_Knuth
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth–Bendix_completion_algorithm
rdf:type
yago:System104377057 yago:Object100002684 yago:Whole100003553 yago:Instrumentality103575240 yago:PhysicalEntity100001930 yago:WikicatRewritingSystems dbo:Software yago:Artifact100021939
rdfs:label
クヌース・ベンディックス完備化アルゴリズム Complétion de Knuth-Bendix Knuth–Bendix completion algorithm
rdfs:comment
La procédure de complétion de Knuth-Bendix ou complétion de Knuth-Bendix (aussi appelée algorithme de Knuth-Bendix ) transforme, si elle réussit, un ensemble fini d'identités (sur des termes) décrivant une structure algébrique en un système de réécriture de termes confluent et qui termine (dit alors convergent). Le processus de complétion a été inventé par Donald Knuthaidé d'un étudiant, nommé Peter Bendix, pour la mise en œuvre. クヌース・ベンディックス完備化アルゴリズム（英: Knuth–Bendix completion algorithm）、あるいはクヌース・ベンディックス完備化手続きは、等式の有限集合をそれと等価な完備性のある項書き換えシステムに変換するアルゴリズムである。このアルゴリズムは普遍代数（en）での語の問題（word problem）（en）を解くための手法としてクヌースとベンディックスから提案された。アルゴリズムは必ず成功するとは限らないが、成功した場合は停止性と合流性のある項書き換えシステムを生成することができる。そのベースとなる考え方は多くの分野で応用することができる。 The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra. Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings.
dcterms:subject
dbc:Combinatorics_on_words dbc:Donald_Knuth dbc:Rewriting_systems dbc:Computational_group_theory
dbo:wikiPageID
614147
dbo:wikiPageRevisionID
1117289232
dbo:wikiPageWikiLink
dbr:Equation dbr:Encompassment_ordering dbr:Normal_form_(term_rewriting) dbr:Converse_relation dbr:Variant_(logic) dbr:Buchberger's_algorithm dbr:Newman's_lemma dbr:Semidecidable dbr:Free_Abelian_group dbr:Polynomial_ring dbr:Coset dbr:Convergent_term_rewrite_system dbr:Relation_(mathematics) dbr:Algebra dbr:Critical_pair_(logic) dbr:Finitely_presented_monoid dbr:Donald_E._Knuth dbr:Logged_rewriting dbr:Semi-algorithm dbr:Reduction_ordering dbr:Computational_group_theory dbr:Finitely_presented_group dbc:Rewriting_systems dbc:Combinatorics_on_words dbr:Resolution_(logic) dbc:Donald_Knuth dbr:Group_(mathematics) dbr:Confluence_(abstract_rewriting) dbr:Shortlex_order dbr:Word_problem_(mathematics) dbr:Presentation_of_a_group dbr:Binary_relation dbr:Ground_confluent dbr:E_theorem_prover dbr:Critical_pair_lemma dbc:Computational_group_theory dbr:Generating_set_of_a_group dbr:Confluence_(term_rewriting) dbr:Equivalence_closure dbr:Reflexive_transitive_closure dbr:Term_(logic) dbr:Algorithm dbr:Gröbner_basis dbr:Rewrite_closure dbr:Relation_composition dbr:Term_rewriting_system dbr:Well-ordered
dbo:wikiPageExternalLink
n16: n18:knuth-bendix.pdf n20:books%3Fhl=en&lr=&id=UytXH6rLUDwC&oi=fnd&pg=PA256&dq=%22Logged+rewriting+and+identities+among+relators%22&ots=KYif_N4FmE&sig=We5TmSZlfdt1o8Xyxg1AYF1A4Vk%23v=onepage&q&f=false n22:RR-0025.pdf%7C
owl:sameAs
dbpedia-fr:Complétion_de_Knuth-Bendix wikidata:Q2835803 dbpedia-ja:クヌース・ベンディックス完備化アルゴリズム n19:2e2w7 freebase:m.02wqch
dbp:wikiPageUsesTemplate
dbt:Cite_journal dbt:Mvar dbt:Mset dbt:Overunderset dbt:EquationRef dbt:Reflist dbt:NumBlk dbt:Math dbt:MathWorld dbt:Cite_book dbt:Underset dbt:EquationNote dbt:Donald_Knuth_navbox
dbp:title
Knuth–Bendix Completion Algorithm
dbp:urlname
Knuth-BendixCompletionAlgorithm
dbo:abstract
La procédure de complétion de Knuth-Bendix ou complétion de Knuth-Bendix (aussi appelée algorithme de Knuth-Bendix ) transforme, si elle réussit, un ensemble fini d'identités (sur des termes) décrivant une structure algébrique en un système de réécriture de termes confluent et qui termine (dit alors convergent). Le processus de complétion a été inventé par Donald Knuthaidé d'un étudiant, nommé Peter Bendix, pour la mise en œuvre. En cas de réussite, la complétion donne un moyen effectif de résoudre le problème du mot pour l'algèbre en question, comme cela a été démontré par Gérard Huet. Par exemple, pour la théorie équationnelle des groupes (voir schéma à droite), la complétion fournit un système de réécriture de terme confluent et qui termine. On peut alors décider si une équation t1 = t2 est vraie dans tous les groupes (même si décider si une formule du premier ordre est vraie dans tous les groupes est indécidable). Malheureusement, le problème du mot étant indécidable en général, la procédure de complétion ne se termine pas toujours avec succès. Elle peut soit s'exécuter indéfiniment, soit échouer en rencontrant une identité non-orientable (qu'elle ne peut pas transformer en règle de réécriture sans être sûre de ne pas mettre en danger la terminaison). Il existe une variante de la procédure de complétion qui n'échoue pas sur les identités non orientables. Elle fournit une procédure de semi-décision pour le problème du mot, autrement dit, elle permet de dire si une identité donnée est déductible des identités qui décrivent l'algèbre en question, dans tous les cas où elle l'est effectivement, mais peut ne jamais terminer. クヌース・ベンディックス完備化アルゴリズム（英: Knuth–Bendix completion algorithm）、あるいはクヌース・ベンディックス完備化手続きは、等式の有限集合をそれと等価な完備性のある項書き換えシステムに変換するアルゴリズムである。このアルゴリズムは普遍代数（en）での語の問題（word problem）（en）を解くための手法としてクヌースとベンディックスから提案された。アルゴリズムは必ず成功するとは限らないが、成功した場合は停止性と合流性のある項書き換えシステムを生成することができる。そのベースとなる考え方は多くの分野で応用することができる。 The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra. Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings.
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Knuth–Bendix_completion_algorithm?oldid=1117289232&ns=0
dbo:wikiPageLength
21397
foaf:isPrimaryTopicOf
wikipedia-en:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Completion
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageDisambiguates
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth-Bendix_completion_algorithm
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth_Bendix_completion
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth_Bendix_completion_algorithm
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth-Bendix
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth-Bendix_algorithm
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth-Bendix_completion
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth–Bendix_algorithm
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
dbr:Knuth–Bendix_completion
dbo:wikiPageWikiLink
dbr:Knuth–Bendix_completion_algorithm
dbo:wikiPageRedirects
dbr:Knuth–Bendix_completion_algorithm
Subject Item
wikipedia-en:Knuth–Bendix_completion_algorithm
foaf:primaryTopic
dbr:Knuth–Bendix_completion_algorithm