The search session has expired. Please query the service again.
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...
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....
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....
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...
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...
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...
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 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 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