-
The sequences which have trivial prefix-free initial segment
complexity are known as K-trivial sets, and form a cumulative
hierarchy of length ~. We show that the problem of finding the number
of K-trivial sets in the various levels of the hierarchy is
~^0_3. This answers a question of Downey/Mil...
-
-
An infinite sequence X is said to have trivial (prefix-free) initial
segment complexity if K(X~n) ~+ K(0^n) for all n, where K is the
prefix-free complexity and ~+ denotes inequality modulo a constant. In
other words, if the information in any initial segment of it is merely
the information in a ...
-
If a computer is given access to an oracle—the characteristic
function of a set whose membership relation may or may not be
algorithmically calculable—this may dramatically affect its ability to
compress information and to determine structure in strings which might
otherwise appear random. This l...
-
This brief note compares a few ways of deriving pre-orders over sets
of objects from strict partial orders over properties of those objects
—so-called priority graphs that have recently been used by logicians
as a rich explicit model of preference merge, belief revision, norm
change, and other as...
-
Aiming at a formal representation of narratives that captures the
intuitive notion of being the same story, we discuss the comparison of
two different formal frameworks.
-
We present a method for using standard techniques from satisfiability
checking to automatically verify and discover theorems in an area of
economic theory known as ranking sets of objects. The key question in
this area, which has important applications in social choice theory
and decision making ...
-
We answer a question of Jockusch by showing that the measure of the
Turing degrees which satisfy the cupping property is 0. In fact, every
2-random degree has a strong minimal cover, and so fails to satisfy
the cupping property.
-
Boolean games are a natural, compact, and expressive class of
logic-based games, in which each player exercises unique control over
some set of Boolean variables, and has some logical goal formula that
it desires to be achieved. A player’s strategy set is the set of all
possible valuations that m...
-
We introduce an atomic formula \vec{y} ⊥_\vec{x} \vec{z} intuitively
saying that the variables \vec{y} are independent from the variables
\vec{z} if the variables \vec{x} are kept constant. We contrast this
with dependence logic D based on the atomic formula =(\vec{x},
\vec{y}), actually a specia...
-
In Aristotelian logic, the predominant view has always been that there
are only two kinds of quantities: universal and particular. For this
reason, philosophers have struggled with singular propositions (e.g.,
``Socrates is running''). One modern approach to this problem, as
first proposed in 195...