About: Bekić's theorem

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

In computability theory, Bekić's theorem or Bekić's lemma is a theorem about fixed-points which allows splitting a mutual recursion into recursions on one variable at a time. It was created by Hans Bekić in 1969, and published posthumously in a book by Cliff Jones in 1984. Bekić's theorem (called the "bisection lemma" in his notes) is that the simultaneous least fixed point can be separated into a series of least fixed points on and , in particular: Proof (Bekić):

Property Value
dbo:abstract
  • In computability theory, Bekić's theorem or Bekić's lemma is a theorem about fixed-points which allows splitting a mutual recursion into recursions on one variable at a time. It was created by Hans Bekić in 1969, and published posthumously in a book by Cliff Jones in 1984. The theorem is set up as follows. Consider two operators and on pointed directed-complete partial orders and , continuous in each component. Then define the operator . This is monotone with respect to the product order (componentwise order). By the Kleene fixed-point theorem, it has a least fixed point , a pair in such that and . Bekić's theorem (called the "bisection lemma" in his notes) is that the simultaneous least fixed point can be separated into a series of least fixed points on and , in particular: Proof (Bekić): since it is the fixed point. Similarly . Hence is a fixed point of . Conversely, if there is a pre-fixed point with , then and ; hence and is the minimal fixed point. (en)
dbo:wikiPageID
  • 70253847 (xsd:integer)
dbo:wikiPageLength
  • 5651 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1115436343 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In computability theory, Bekić's theorem or Bekić's lemma is a theorem about fixed-points which allows splitting a mutual recursion into recursions on one variable at a time. It was created by Hans Bekić in 1969, and published posthumously in a book by Cliff Jones in 1984. Bekić's theorem (called the "bisection lemma" in his notes) is that the simultaneous least fixed point can be separated into a series of least fixed points on and , in particular: Proof (Bekić): (en)
rdfs:label
  • Bekić's theorem (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
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