Object Complexity

• Autorzy: Szczypka E.
• Języki publikacji: EN

Abstrakty

EN

The publications are sources concerning the complexity of algorithms in respect of the complexity of input data are rather scarce, even though it is quite obvious that the complexity of algorithms strongly depends on the complexity of input data. At the same time expressions like 'almost all' or 'a certain part of' are commonly used in terminology concerning probabilistic algorithms and methods. In this paper we will attempt to take a closer look at what these expressions actually mean. Therefore we will aim to develop and systematize the theory of complexity functions.

Słowa kluczowe

EN

lambda calculus; complexity function

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2004
• Tom: Vol. 13
• Strony: 165--177
• Opis fizyczny: Bibliogr. 4 poz.

Twórcy

autor

Szczypka E.

• Institute of Computer Science, Jagiellonian University, Nawojki 11, 30-072 Kraków Poland,

Bibliografia

• [1] Burris S.; Number theoretic density and logical limit laws, American Mathematical Society, Providence, RI, 2001.
• [2]Moczurad M., Tyszkiewicz J., Zaionc M.; Statistical properties of simple types, Mathematical Structures in Computer Science, 10, 2000, pp. 575-594.
• [3]Kozik J.; Asymptotyczne gęstości języków regularnych, Institute of Computer Science, Jagiellonian University, Cracow, Poland, 2002 (in Polish).
• [4] Kozik M.; Measurements of object complexity, Institute of Computer Science, Jagiellonian University, Cracow, Poland, 2000.