Model theory for infinite quantifier languages
Tapani Hyttinen (1990)
Fundamenta Mathematicae
Similarity:
Tapani Hyttinen (1990)
Fundamenta Mathematicae
Similarity:
Martin Weese (1980)
Fundamenta Mathematicae
Similarity:
F. Blanchet-Sadri (1990)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Victor L. Selivanov (2009)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an...
Martin Lange (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
This paper analyses the complexity of model checking fixpoint logic with Chop – an extension of the modal -calculus with a sequential composition operator. It uses two known game-based characterisations to derive the following results: the combined model checking complexity as well as the data complexity of FLC are EXPTIME-complete. This is already the case for its alternation-free fragment. The expression complexity of FLC is trivially P-hard and limited from above by the complexity...
Jérémie Cabessa, Jacques Duparc (2009)
RAIRO - Theoretical Informatics and Applications
Similarity:
The algebraic study of formal languages shows that -rational sets correspond precisely to the -languages recognizable by finite -semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the -rational language to the -semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation...
Blondel, Vincent D., Hendrickx, Julien M., Jungers, Raphaël M. (2008)
Integers
Similarity:
Julian C. Bradfield (2003)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over . This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.