Local normal forms for first-order logic with applications to games and automata.

Schwentick, Thomas; Barthelmann, Klaus

The search session has expired. Please query the service again.

Displaying similar documents to “Local normal forms for first-order logic with applications to games and automata.”

Finite models and finitely many variables

Anuj Dawar (1999)

Banach Center Publications

Similarity:

This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.

On independence-friendly fixpoint logics

J. C. Bradfield (2004)

Philosophia Scientiae

Similarity:

We introduce a fixpoint extension of Hintikka and Sandu’s IF (independence-friendly) logic. We obtain some results on its complexity and expressive power. We relate it to parity games of imperfect information, and show its application to defining independence-friendly modal mu-calculi.

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2004)

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

Similarity:

We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...

The Properties of Sets of Temporal Logic Subformulas

Mariusz Giero (2012)

Formalized Mathematics

Similarity:

This is a second preliminary article to prove the completeness theorem of an extension of basic propositional temporal logic. We base it on the proof of completeness for basic propositional temporal logic given in [17]. We introduce two modified definitions of a subformula. In the former one we treat until-formula as indivisible. In the latter one, we extend the set of subformulas of until-formulas by a special disjunctive formula. This is needed to construct a temporal model. We also...

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...

ω-Trees in stationary logic

A. Baudisch, D. Sesse, H. Tuschik (1983)

Fundamenta Mathematicae

Similarity:

Weak Completeness Theorem for Propositional Linear Time Temporal Logic

Mariusz Giero (2012)

Formalized Mathematics

Similarity:

We prove weak (finite set of premises) completeness theorem for extended propositional linear time temporal logic with irreflexive version of until-operator. We base it on the proof of completeness for basic propositional linear time temporal logic given in [20] which roughly follows the idea of the Henkin-Hasenjaeger method for classical logic. We show that a temporal model exists for every formula which negation is not derivable (Satisfiability Theorem). The contrapositive of that...

Reasoning in Basic Description Logics and Description Logics with Modal Operators

Milenko Mosurović, Tatjana Stojanović, Ana Kaplarević-Mališić (2009)

Zbornik Radova

Similarity:

On completeness results for Predicate Lukasiewicz, Product, Gödel and Nilpotent Minimum Logics Expanded with Truth-constants.

F. Esteva, L. Godo, C. Noguera (2007)

Mathware and Soft Computing

Similarity: