All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 21

Showing per page

Advice Complexity and Barely Random Algorithms

Dennis Komm, Richard Královič (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our...

Advice Complexity and Barely Random Algorithms

Dennis Komm, Richard Královič (2011)

RAIRO - Theoretical Informatics and Applications

Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization....

Applying A Normalized Compression Metric To The Measurement Of Dialect Distance

Simov, Kiril, Osenova, Petya (2007)

Serdica Journal of Computing

The paper discusses the application of a similarity metric based on compression to the measurement of the distance among Bulgarian dia- lects. The similarity metric is de ned on the basis of the notion of Kolmo- gorov complexity of a le (or binary string). The application of Kolmogorov complexity in practice is not possible because its calculation over a le is an undecidable problem. Thus, the actual similarity metric is based on a real life compressor which only approximates the Kolmogorov complexity....

Kolmogorov complexity and probability measures

Jan Šindelář, Pavel Boček (2002)

Kybernetika

Classes of strings (infinite sequences resp.) with a specific flow of Kolmogorov complexity are introduced. Namely, lower bounds of Kolmogorov complexity are prescribed to strings (initial segments of infinite sequences resp.) of specified lengths. Dependence of probabilities of the classes on lower bounds of Kolmogorov complexity is the main theme of the paper. Conditions are found under which the probabilities of the classes of the strings are close to one. Similarly, conditions are derived under...

Kolmogorov complexity, pseudorandom generators and statistical models testing

Jan Šindelář, Pavel Boček (2002)

Kybernetika

An attempt to formalize heuristic concepts like strings (sequences resp.) “typical” for a probability measure is stated in the paper. Both generating and testing of such strings is considered. Kolmogorov complexity theory is used as a tool. Classes of strings “typical” for a given probability measure are introduced. It is shown that no pseudorandom generator can produce long strings from the classes. The time complexity of pseudorandom generators with oracles capable to recognize “typical” strings...

PAC learning under helpful distributions

François Denis, Rémi Gilleron (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A PAC teaching model – under helpful distributions – is proposed which introduces the classical ideas of teaching models within the PAC setting: a polynomial-sized teaching set is associated with each target concept; the criterion of success is PAC identification; an additional parameter, namely the inverse of the minimum probability assigned to any example in the teaching set, is associated with each distribution; the learning algorithm running time takes this new parameter into account. An Occam...

PAC Learning under Helpful Distributions

François Denis, Rémi Gilleron (2010)

RAIRO - Theoretical Informatics and Applications

A PAC teaching model -under helpful distributions -is proposed which introduces the classical ideas of teaching models within the PAC setting: a polynomial-sized teaching set is associated with each target concept; the criterion of success is PAC identification; an additional parameter, namely the inverse of the minimum probability assigned to any example in the teaching set, is associated with each distribution; the learning algorithm running time takes this new parameter into account. ...

The entropy of Łukasiewicz-languages

Ludwig Staiger (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.

The entropy of Łukasiewicz-languages

Ludwig Staiger (2010)

RAIRO - Theoretical Informatics and Applications

The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.

Currently displaying 1 – 20 of 21

Page 1 Next