NBC News Scripts
WBAP-TV (Television station : Fort Worth, Tex.)
1954-12-31
Search results
12 records were found.
The coalgebraic approach to modal logic provides a uniform framework
that captures the semantics of a large class of structurally different modal
logics, including e.g. graded and probabilistic modal logics and coalition logic.
In this paper, we introduce the coalgebraic mu-calculus, an extension of the general
(coalgebraic) framework with fixpoint operators. Our main results are completeness
of the associated tableau calculus and EXPTIME decidability. Technically,
this is achieved by reducing satisfiability to the existence of non-wellfounded
tableaux, which is in turn equivalent to the existence of winning strategies in
parity games. Our results are parametric in the underlying class of models and
yield, as concrete applications, previously unknown complexity bounds for the
probabilistic mu-calculus and for an extension of ...
The coalgebraic approach to modal logic provides a uniform framework that captures the semantics of a large class of structurally different modal logics, including e.g. graded and probabilistic modal logics and coalition logic. In this paper, we introduce the coalgebraic mu-calculus, an extension of the general (coalgebraic) framework with fixpoint operators. Our main results are completeness of the associated tableau calculus and EXPTIME decidability. Technically, this is achieved by reducing satisfiability to the existence of non-wellfounded tableaux, which is in turn equivalent to the existence of winning strategies in parity games. Our results are parametric in the underlying class of models and yield, as concrete applications, previously unknown complexity bounds for the probabilistic mu-calculus and for an extension of coalition ...
We discuss several notions of "simple" winning strategies for
Banach-Mazur games on graphs, such as positional strategies,
move-counting or length-counting strategies, and strategies with a
memory based on finite appearance records (FAR). We investigate
classes of Banach-Mazur games that are determined via these kinds of
winning strategies.
Banach-Mazur games admit stronger determinacy results than classical
graph games. For instance, all Banach-Mazur games with omega-regular
winning conditions are positionally determined. Beyond the
omega-regular winning conditions, we focus here on Muller conditions
with infinitely many colours. We investigate the infinitary Muller
conditions that guarantee positional determinacy for Banach-Mazur
games. Further, we determine classes of such conditions that require
infinite memory but guarantee dete...
Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matrices over finite fields. While FPR can express most of the known queries that separate FPC from PTIME, nearly nothing was known about the limitations of its expressive power.
In our first main result we show that the extensions of FPC by rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic FPR* with an operator that uniformly expresses the matrix rank over finite fields is more expressive than FPR.
One impo...
We explore several counting constructs for logics with team semantics. Counting is an important task in numerous applications, but with a somewhat delicate relationship to logic. Team semantics on the other side is the mathematical basis of modern logics of dependence and independence, in which formulae are evaluated not for a single assignment of values to variables, but for a set of such assignments. It is therefore interesting to ask what kind of counting constructs are adequate in this context, and how such constructs influence the expressive power, and the model-theoretic and algorithmic properties of logics with team semantics. Due to the second-order features of team semantics there is a rich variety of potential counting constructs. Here we study variations of two main ideas: forking atoms and counting quantifiers.
Forking cou...
We investigate quantitative extensions of modal logic and the modal
$mu$-calculus, and study the question whether the tight connection
between logic and games can be lifted from the qualitative logics
to their quantitative counterparts. It turns out that, if the
quantitative $mu$-calculus is defined in an appropriate way
respecting the duality properties between the logical operators,
then its model checking problem can indeed be characterised by a
quantitative variant of parity games. However, these quantitative
games have quite different properties than their classical
counterparts, in particular they are, in general, not positionally
determined. The correspondence between the logic and the games
goes both ways: the value of a formula on a quantitative transition
system coincides with the value ...
We investigate structural properties of omega-automatic presentations of infinite structures in order to sharpen our methods to determine whether a given structure is omega-automatic. We apply these methods to show that no field of characteristic 0 admits an injective omega-automatic presentation, and that uncountable fields with a definable linear order cannot be omega-automatic.
We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory.
Specifically, we show that the power of several propositional proof systems, such as Horn resolution, bounded width resolution, and the polynomial calculus of bounded degree, can be characterised in a precise sense by variants of fixed-point logics that are of fundamental importance in descriptive complexity theory.
Our main results are that Horn resolution has the same expressive power as least fixed-point logic, that bounded width resolution captures existential least fixed-point logic, and that the (monomial restriction of the) polynomial calculus of bounded degree solves precisely the problems definable in fixed-point logic with counting.
We study structures that are automatic with advice. These are structures that admit a presentation by finite automata (over finite or infinite words or trees) with access to an additional input,called an advice. Over finite words, a standard example of a structure that is automatic with advice, but not automatic in the classical sense, is the additive group of rational numbers (Q,+).
By using a set of advices rather than a single advice, this leads to the new concept of a parameterised automatic presentation as a means to uniformly represent a whole class of structures. The decidability of the first-order theory of such a uniformly automatic class reduces to the decidability of the monadic second-order theory of the set of advices that are used in the presentation. Such decidability results also hold for extensions of first-order logic...
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. All problems that we consider are decidable in polynomial time, but not expressible in fixed-point logic with counting. They also provide natural candidates for a separation of polynomial time from rank logics, which extend fixed-point logics by operators for determining the rank of definable matrices and which are sufficient for solvability problems over fields.
Based on the structure theory of finite rings, we establish logical reductions among various solvability problems. Our results indicate that all solvability problems for linear equa...
