Tarski–Kuratowski algorithm

Tarski–Kuratowski algorithm

In computability theory and mathematical logic the Tarski–Kuratowski algorithm is a non-deterministic algorithm which provides an upper bound for the complexity of formulas in the arithmetical hierarchy and analytical hierarchy.

The algorithm is named after Alfred Tarski and Kazimierz Kuratowski.

References

*Rogers, H. "The Theory of Recursive Functions and Effective Computability", MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Kazimierz Kuratowski — TOCleftKazimierz Kuratowski (Warsaw, February 2, 1896 ndash;June 18, 1980) was a Polish mathematician and logician.BiographyKuratowski was born a subject of Tsarist Russia. In 1913, he enrolled in an engineering course at the University of… …   Wikipedia

  • Alfred Tarski — Infobox scientist name = Alfred Tarski caption = birth date = birth date|1901|01|14 birth place = Warsaw, Poland (under Russian rule at the time) death date = death date|1983|10|26 death place = Berkeley, California fields = Mathematics, logic,… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Arithmetical hierarchy — In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The… …   Wikipedia

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

  • List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) …   Wikipedia

  • logic, history of — Introduction       the history of the discipline from its origins among the ancient Greeks to the present time. Origins of logic in the West Precursors of ancient logic       There was a medieval tradition according to which the Greek philosopher …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”