Displaying 21 – 40 of 61

Showing per page

Domain mu-calculus

Guo-Qiang Zhang (2003)

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

The basic framework of domain μ -calculus was formulated in [39] more than ten years ago. This paper provides an improved formulation of a fragment of the μ -calculus without function space or powerdomain constructions, and studies some open problems related to this μ -calculus such as decidability and expressive power. A class of language equations is introduced for encoding μ -formulas in order to derive results related to decidability and expressive power of non-trivial fragments of the domain μ -calculus....

Domain mu-calculus

Guo-Qiang Zhang (2010)

RAIRO - Theoretical Informatics and Applications

The basic framework of domain μ-calculus was formulated in [39] more than ten years ago. This paper provides an improved formulation of a fragment of the μ-calculus without function space or powerdomain constructions, and studies some open problems related to this μ-calculus such as decidability and expressive power. A class of language equations is introduced for encoding μ-formulas in order to derive results related to decidability and expressive power of non-trivial fragments of the domain...

Fixpoints, games and the difference hierarchy

Julian C. Bradfield (2003)

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

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 Σ 2 0 . 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.

Fixpoints, games and the difference hierarchy

Julian C. Bradfield (2010)

RAIRO - Theoretical Informatics and Applications

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 Σ 2 0 . 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.

Idealized coinductive type systems for imperative object-oriented programs

Davide Ancona, Giovanni Lagorio (2011)

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

In recent work we have proposed a novel approach to define idealized type systems for object-oriented languages, based on abstract compilation of programs into Horn formulas which are interpreted w.r.t. the coinductive (that is, the greatest) Herbrand model. In this paper we investigate how this approach can be applied also in the presence of imperative features. This is made possible by considering a natural translation of Static Single Assignment intermediate form programs into Horn formulas,...

Idealized coinductive type systems for imperative object-oriented programs

Davide Ancona, Giovanni Lagorio (2011)

RAIRO - Theoretical Informatics and Applications

In recent work we have proposed a novel approach to define idealized type systems for object-oriented languages, based on abstract compilation of programs into Horn formulas which are interpreted w.r.t. the coinductive (that is, the greatest) Herbrand model. In this paper we investigate how this approach can be applied also in the presence of imperative features. This is made possible by considering a natural translation of Static Single Assignment intermediate form programs into Horn formulas,...

Many-sorted coalgebraic modal logic : a model-theoretic study

Bart Jacobs (2001)

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

This paper gives a semantical underpinning for a many-sorted modal logic associated with certain dynamical systems, like transition systems, automata or classes in object-oriented languages. These systems will be described as coalgebras of so-called polynomial functors, built up from constants and identities, using products, coproducts and powersets. The semantical account involves Boolean algebras with operators indexed by polynomial functors, called MBAOs, for Many-sorted Boolean Algebras with...

Many-Sorted Coalgebraic Modal Logic: a Model-theoretic Study

Bart Jacobs (2010)

RAIRO - Theoretical Informatics and Applications

This paper gives a semantical underpinning for a many-sorted modal logic associated with certain dynamical systems, like transition systems, automata or classes in object-oriented languages. These systems will be described as coalgebras of so-called polynomial functors, built up from constants and identities, using products, coproducts and powersets. The semantical account involves Boolean algebras with operators indexed by polynomial functors, called MBAOs, for Many-sorted Boolean Algebras with...

On characteristic formulae for Event-Recording Automata

Omer Landry Nguena Timo, Pierre-Alain Reynier (2013)

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

A standard bridge between automata theory and logic is provided by the notion of characteristic formula. This paper investigates this problem for the class of event-recording automata (ERA), a subclass of timed automata in which clocks are associated with actions and that enjoys very good closure properties. We first study the problem of expressing characteristic formulae for ERA in Event-Recording Logic (ERL ), a logic introduced by Sorea to express event-based timed specifications. We prove that...

On Core XPath with Inflationary Fixed Points

Loredana Afanasiev, Balder Ten Cate (2013)

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

We prove the undecidability of Core XPath 1.0 (CXP) [G. Gottlob and C. Koch, in Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS ’02 (Copenhagen, July 2002). IEEE CS Press (2002) 189–202.] extended with an Inflationary Fixed Point (IFP) operator. More specifically, we prove that the satisfiability problem of this language is undecidable. In fact, the fragment of CXP+IFP containing only the self and descendant axes is already undecidable.

Currently displaying 21 – 40 of 61