All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 5 of 5

Showing per page

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 1 – 5 of 5

Page 1