Selected publications by Stéphane Demri

2012

• S. Demri, D. D'Souza and R. Gascon.  Temporal Logics of Repeating Values.  Journal of Logic and Computation, 2012. To appear. ( PDF | BibTeX + Abstract )
• R. Brochenin, S. Demri and É. Lozes.  On the Almighty Wand.  Information and Computation 211, pages 106-137, 2012. ( PDF | BibTeX + Abstract )

2011

• P. Cabalar and S. Demri.  Automata-Based Computation of Temporal Equilibrium Models.  In LOPSTR'11, LNCS. Springer, 2011. To appear. ( PDF | BibTeX + Abstract )
• S. Demri and P. Gastin.  Specification and Verification using Temporal Logics.  In Modern applications of automata theory, IISc Research Monographs 2. World Scientific, 2011. To appear. ( PDF | BibTeX + Abstract )
• S. Demri and D. Poitrenaud.  Verification of Infinite-State Systems.  In Models and Analysis in Distributed Systems, chapter 8, pages 221-269. John Wiley & Sons, Ltd., 2011. ( BibTeX )
• Ph. Darondeau, S. Demri, R. Meyer and Ch. Morvan.  Petri Net Reachability Graphs: Decidability Status of FO Properties.  In FSTTCS'11, Leibniz International Proceedings in Informatics, pages 140-151. Leibniz-Zentrum für Informatik, 2011. ( PDF | BibTeX + Abstract )
• M. Bersani and S. Demri.  The complexity of reversal-bounded model-checking.  In FroCoS'11, LNAI 6989, pages 71-86. Springer, 2011. ( PDF | PDF (long version) | BibTeX + Abstract )

2010

• S. Demri, A. Finkel, V. Goranko and G. van Drimmelen.  Model-checking CTL^* over Flat Presburger Counter Systems.  Journal of Applied Non-Classical Logics 20(4), pages 313-344, 2010. ( PDF | BibTeX + Abstract )
• S. Demri and A. Rabinovich.  The Complexity of Linear-time Temporal Logic over the Class of Ordinals.  Logical Methods in Computer Science 6(4), 2010. ( PDF | BibTeX + Abstract )
• S. Demri.  On Selective Unboundedness of VASS.  In INFINITY'10, Electronic Proceedings in Theoretical Computer Science 39, pages 1-15. 2010. ( PDF | PDF (long version) | BibTeX + Abstract )
• S. Demri and D. Lugiez.  Complexity of Modal Logics with Presburger Constraints.  Journal of Applied Logic 8(3), pages 233-252, 2010. ( PDF | BibTeX + Abstract )
• S. Demri, R. Lazic and A. Sangnier.  Model checking memoryful linear-time logics over one-counter automata.  Theoretical Computer Science 411(22-24), pages 2298-2316, 2010. ( PDF | BibTeX + Abstract )
• S. Demri and A. Sangnier.  When Model-Checking Freeze LTL over Counter Machines Becomes Decidable.  In FoSSaCS'10, LNCS 6014, pages 176-190. Springer, 2010. ( PDF | BibTeX + Abstract )

2009

• R. Brochenin, S. Demri and É. Lozes.  Reasoning about sequences of memory states.  Annals of Pure and Applied Logics 161(3), pages 305-323, 2009. ( PDF | BibTeX + Abstract )
• S. Demri and R. Gascon.  The Effects of Bounding Syntactic Resources on Presburger LTL.  Journal of Logic and Computation 19(6), pages 1541-1575, 2009. ( PDF | BibTeX + Abstract )
• S. Demri, M. Jurdziński, O. Lachish and R. Lazic.  The covering and boundedness problems for branching vector addition systems.  In FSTTCS'09, Leibniz International Proceedings in Informatics 4, pages 181-192. Leibniz-Zentrum für Informatik, 2009. ( PDF | BibTeX + Abstract )
• S. Demri and R. Lazic.  LTL with the freeze quantifier and register automata.  ACM Transactions on Computational Logic 10(3), 2009. ( PDF | BibTeX + Abstract )
• C. Areces and S. Demri (eds.).  Proceedings of the 5th International Workshop on Methods for Modalities (M4M-5), Cachan, France, November 2007, ENTCS 231. Elsevier Science Publishers, 2009. ( BibTeX )

2008

• S. Demri and R. Gascon.  Verification of Qualitative Z constraints.  Theoretical Computer Science 409(1), pages 24-40, 2008. ( PDF | BibTeX + Abstract )
• R. Brochenin, S. Demri and É. Lozes.  On the Almighty Wand.  In CSL'08, LNCS 5213, pages 323-338. Springer, 2008. ( PDF | BibTeX + Abstract )
• S. Demri and Ch. S. Jensen (eds.).  Proceedings of the 15th International Symposium on Temporal Representation and Reasoning (TIME'08), Montréal, Canada, June 2008. IEEE Computer Society Press. ( BibTeX )
• S. Demri, R. Lazic and A. Sangnier.  Model checking freeze LTL over one-counter automata.  In FoSSaCS'08, LNCS 4962, pages 490-504. Springer, 2008. ( PDF | PS | PS.GZ | BibTeX + Abstract )

2007

• S. Demri and E. Orłowska.  Relative Nondeterministic Information Logic is EXPTIME-complete.  Fundamenta Informaticae 75(1-4), pages 163-178, 2007. ( PDF | BibTeX + Abstract )
• S. Demri and A. Rabinovich.  The complexity of temporal logic with until and since over ordinals.  In LPAR'07, LNAI 4790, pages 531-545. Springer, 2007. ( PDF | BibTeX + Abstract )
• R. Brochenin, S. Demri and É. Lozes.  Reasoning about sequences of memory states.  In LFCS'07, LNCS 4514, pages 100-114. Springer, 2007. ( PDF | PDF (long version) | BibTeX + Abstract )
• S. Demri.  Logiques pour la spécification et vérification.  Mémoire d'habilitation, Université Paris 7, Paris, France, June 2007. ( PDF | BibTeX )
• S. Demri, D. D'Souza and R. Gascon.  Decidable Temporal Logic with Repeating Values.  In LFCS'07, LNCS 4514, pages 180-194. Springer, 2007. ( PDF | PDF (long version) | BibTeX + Abstract )
• S. Demri and R. Gascon.  The Effects of Bounding Syntactic Resources on Presburger LTL (Extended Abstract).  In TIME'07, pages 94-104. IEEE Computer Society Press, 2007. ( PDF | BibTeX + Abstract )
• S. Demri and D. D'Souza.  An automata-theoretic approach to constraint LTL.  Information and Computation 205(3), pages 380-415, 2007. ( PDF | BibTeX + Abstract )
• S. Demri and D. Nowak.  Reasoning about transfinite sequences.  International Journal of Foundations of Computer Science 18(1), pages 87-112, 2007. ( PDF | PS | PS.GZ | BibTeX + Abstract )
• S. Demri, R. Lazic and D. Nowak.  On the freeze quantifier in constraint LTL: Decidability and complexity.  Information and Computation 205(1), pages 2-24, 2007. ( PDF | BibTeX + Abstract )

2006

• S. Demri.  Linear-Time Temporal logics with Presburger Constraints: An Overview.  Journal of Applied Non-Classical Logics 16(3-4), pages 311-347, 2006. ( PDF | BibTeX + Abstract )
• S. Demri, A. Finkel, V. Goranko and G. van Drimmelen.  Towards a model-checker for counter systems.  In ATVA'06, LNCS 4218, pages 493-507. Springer, 2006. ( PDF | BibTeX + Abstract )
• S. Demri.  LTL over integer periodicity constraints.  Theoretical Computer Science 360(1-3), pages 96-123, 2006. ( PDF | BibTeX + Abstract )
• S. Demri and R. Lazic.  LTL with the freeze quantifier and register automata.  In LICS'06, pages 17-26. IEEE Computer Society Press, 2006. ( PDF | BibTeX + Abstract )
• S. Demri and D. Lugiez.  Presburger Modal Logic is Only PSPACE-complete.  In IJCAR'06, LNAI 4130, pages 541-556. Springer-Verlag, 2006. ( PDF (long version) | BibTeX + Abstract )
• S. Demri, F. Laroussinie and Ph. Schnoebelen.  A Parametric Analysis of the State Explosion Problem in Model Checking.  Journal of Computer and System Sciences 72(4), pages 547-575, 2006. ( PDF | PS | PS.GZ | BibTeX + Abstract )

2005

• S. Demri.  A reduction from DLP to PDL.  Journal of Logic and Computation 15(5), pages 767-785, 2005. ( PDF | BibTeX + Abstract )
• S. Demri and D. Nowak.  Reasoning about transfinite sequences (extended abstract).  In ATVA'05, LNCS 3707, pages 248-262. Springer, 2005. ( PDF | PS | PS.GZ | BibTeX + Abstract )
• S. Demri and R. Gascon.  Verification of Qualitative Z-Constraints.  In CONCUR'05, LNCS 3653, pages 518-532. Springer, 2005. ( PDF | PDF (long version) | PS (long version) | PS.GZ (long version) | BibTeX + Abstract )
• S. Demri and H. de Nivelle.  Deciding Regular Grammar Logics with Converse through First-Order Logic.  Journal of Logic, Language and Information 14(3), pages 289-319, 2005. ( PDF | BibTeX + Abstract )
• S. Demri, R. Lazic and D. Nowak.  On the Freeze Quantifier in Constraint LTL: Decidability and Complexity.  In TIME'05, pages 113-121. IEEE Computer Society Press, 2005. ( PDF | PS | PS.GZ | BibTeX + Abstract )

2004

• S. Demri.  LTL over Integer Periodicity Constraints.  In FoSSaCS'04, LNCS 2987, pages 121-135. Springer, 2004. ( PDF | PS | PS.GZ | BibTeX )

2003

• N. Alechina, S. Demri and M. de Rijke.  A Modal Perspective on Path Constraints.  Journal of Logic and Computation 13(6), pages 939-956, 2003. ( PDF | PS | PS.GZ | BibTeX )
• S. Demri.  A Polynomial-Space Construction of Tree-Like Models for Logics with Local Chains of Modal Connectives.  Theoretical Computer Science 300(1-3), pages 235-258, 2003. ( PDF | PS | PS.GZ | BibTeX )

2002

• S. Demri.  Modal Logics with Weak Forms of Recursion: PSPACE Specimens.  In AiML 2000, pages 113-138. World Scientific, 2002. Invited paper. ( PDF | PS | PS.GZ | BibTeX )
• S. Demri and E. Orłowska.  Incomplete Information: Structure, Inference, Complexity. EATCS Monographs. Springer, 2002. ( Web page | BibTeX )
• S. Demri and U. Sattler.  Automata-Theoretic Decision Procedures for Information Logics.  Fundamenta Informaticae 53(1), pages 1-22, 2002. ( PDF | PS | PS.GZ | BibTeX )
• S. Demri and D. D'Souza.  An Automata-Theoretic Approach to Constraint LTL.  In FSTTCS'02, LNCS 2556, pages 121-132. Springer, 2002. ( PS | PS.GZ | BibTeX )
• S. Demri and R. P. Goré.  Display Calculi for Nominal Tense Logics.  Journal of Logic and Computation 12(6), pages 993-1016, 2002. ( PS | PS.GZ | BibTeX )
• S. Demri and R. P. Goré.  Theoremhood Preserving Maps Characterising Cut Elimination for Modal Provability Logics.  Journal of Logic and Computation 12(5), pages 861-884, 2002. ( PS | PS.GZ | BibTeX )
• S. Demri and Ph. Schnoebelen.  The Complexity of Propositional Linear Temporal Logics in Simple Cases.  Information and Computation 174(1), pages 84-103, 2002. ( PDF | PS | PS.GZ | BibTeX + Abstract )
• S. Demri, F. Laroussinie and Ph. Schnoebelen.  A Parametric Analysis of the State Explosion Problem in Model Checking (Extended Abstract).  In STACS'02, LNCS 2285, pages 620-631. Springer, 2002. ( PDF | PS | PS.GZ | BibTeX + Abstract )

2001

• S. Demri.  Coping with Semilattices of Relations in Logics with Relative Accessibility Relations.  In RelMiCS'98, Studies in Fuzziness and Soft Computing 65, pages 163-181. Springer, 2001. ( PDF | BibTeX )
• S. Demri.  The Complexity of Regularity in Grammar Logics and Related Modal Logics.  Journal of Logic and Computation 11(6), pages 933-960, 2001. ( PDF | PS | PS.GZ | BibTeX )
• N. Alechina, S. Demri and M. de Rijke.  Path Constraints from a Modal Logic Point of View (Extended Abstract).  In KRDB'01, CEUR Workshop Proceedings 45. Technical Universität Aachen, Germany, 2001. ( PS | PS.GZ | BibTeX )

2000

• S. Demri.  A Simple Modal Encoding of Propositional Finite Many-Valued Logics.  Multiple-Valued Logic 6, pages 443-461, 2000. ( PDF | PS | PS.GZ | BibTeX )
• S. Demri and R. P. Goré.  An O((n.log  n)³)-Time Transformation from Grz into Decidable Fragments of Classical First-Order Logic.  In FTP'98, LNAI 1761, pages 153-167. Springer, 2000. ( PDF | BibTeX )
• S. Demri and D. M. Gabbay.  On Modal Logics Characterized by Models with Relative Accessibility Relations: Part II.  Studia Logica 66(3), pages 349-384, 2000. ( PS | PS.GZ | BibTeX )
• S. Demri and J. Stepaniuk.  Computational Complexity of Multimodal Logics Based on Rough Sets.  Fundamenta Informaticae 44(4), pages 373-396, 2000. ( PS | PS.GZ | BibTeX )
• S. Demri and D. M. Gabbay.  On Modal Logics Characterized by Models with Relative Accessibility Relations: Part I.  Studia Logica 65(3), pages 323-353, 2000. ( PS | PS.GZ | BibTeX )
• S. Demri.  Complexity of Simple Dependent Bimodal Logics.  In TABLEAUX 2000, LNAI 1847, pages 190-204. Springer, 2000. ( PS | PS.GZ | BibTeX )
• S. Demri.  The Nondeterministic Information Logic NIL is PSPACE-complete.  Fundamenta Informaticae 42(3-4), pages 211-234, 2000. ( PDF | PS | PS.GZ | BibTeX )
• S. Demri and R. P. Goré.  Display Calculi for Logics with Relative Accessibility Relations.  Journal of Logic, Language and Information 9(2), pages 213-236, 2000. ( PDF | BibTeX )

1999

• S. Demri and E. Orłowska.  Informational Representability: Abstract Models versus Concrete Models.  In Fuzzy sets, Logics and Reasoning about Knowledge, pages 301-314. Kluwer Academic Publishers, 1999. ( BibTeX )
• S. Demri and R. P. Goré.  Tractable Transformations from Modal Provability Logics into First-Order Logic.  In CADE'99, LNCS 1632, pages 16-30. Springer, 1999. ( PS | PS.GZ | BibTeX )
• S. Demri.  Sequent Calculi for Nominal Tense Logics: A Step towards Mechanization?  In TABLEAUX'99, LNAI 1617, pages 140-154. Springer, 1999. ( PDF | BibTeX )
• S. Demri and R. P. Goré.  Cut-Free Display Calculi for Nominal Tense Logics.  In TABLEAUX'99, LNAI 1617, pages 155-170. Springer, 1999. ( BibTeX )
• S. Demri, E. Orłowska and D. Vakarelov.  Indiscernibility and Complementarity Relations in Pawlak's Information Systems.  In JFAK: Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday. 1999. ( PDF | BibTeX )
• S. Demri and E. Orłowska.  Informational representability of models for information logics.  In Logic at Work. Essays Dedicated to the Memory of Helena Rasiowa, Studies in Fuzziness and Soft Computing 24, chapter 22, pages 383-409. Physica Verlag, 1999. ( BibTeX )
• S. Demri and E. Orłowska.  Every Finitely Reducible Logic has the Finite Model Property with Respect to the Class of diamond-Formulae.  Studia Logica 62(2), pages 177-200, 1999. ( PS | PS.GZ | BibTeX )
• S. Demri.  A Logic with Relative Knowledge Operators.  Journal of Logic, Language and Information 8(2), pages 167-185, 1999. ( PS | PS.GZ | BibTeX )

1998

• S. Demri and B. Konikowska.  Relative Similarity Logics are Decidable: Reduction to FO² with Equality.  In JELIA'98, LNAI 1489, pages 279-293. Springer, 1998. ( PS | PS.GZ | BibTeX )
• S. Demri and E. Orłowska.  Complementarity Relations: Reduction of Decision Rules and Informational Representability.  In Rough Sets in Knowledge Discovery - 1. Methodology and Applications, Studies in Fuzziness and Soft Computing 18, chapter 5, pages 99-106. Physica Verlag, 1998. ( BibTeX )
• S. Demri.  A Class of Decidable Information Logics.  Theoretical Computer Science 195(1), pages 33-60, 1998. ( PDF | BibTeX )
• S. Demri and E. Orłowska.  Logical analysis of indiscernibility.  In Incomplete Information: Rough Set Analysis, Studies in Fuzziness and Soft Computing 13, chapter 11, pages 347-380. Physica Verlag, 1998. ( BibTeX )

1997

• Ph. Balbiani and S. Demri.  Prefixed Tableaux Systems for Modal Logics with Enriched Languages.  In IJCAI'97, pages 190-195. Morgan Kaufmann, 1997. ( PS | PS.GZ | BibTeX )
• S. Demri.  A Completeness Proof for a Logic with an Alternative Necessity Operator.  Studia Logica 58(1), pages 99-112, 1997. ( BibTeX )

1996

• S. Demri and E. Orłowska.  Logical Analysis of Demonic Nondeterministic Programs.  Theoretical Computer Science 166(1-2), pages 173-202, 1996. ( PDF | BibTeX )
• S. Demri.  A Class of Information Logics with a Decidable Validity Problem.  In MFCS'96, LNCS 1113, pages 291-302. Springer, 1996. ( BibTeX )
• S. Demri.  A Simple Tableau System for the Logic of Elsewhere.  In TABLEAUX'96, LNAI 1071, pages 177-192. Springer, 1996. ( PDF | BibTeX )

1995

• S. Demri.  Uniform and Non Uniform Strategies for Tableaux Calculi for Modal Logics.  Journal of Applied Non-Classical Logics 5(1), pages 77-96, 1995. ( BibTeX )
• Th. Boy de la Tour and S. Demri.  On the Complexity of Extending Ground Resolution with Symmetry Rules.  In IJCAI'85, pages 289-295. Morgan Kaufmann, 1995. ( PS | PS.GZ | BibTeX )
• S. Demri.  A Hierarchy of Backward Translations: Applications to Modal Logics.  In WOCFAI'95, pages 121-132. Angkor, 1995. ( BibTeX )
• S. Demri.  SAT = 3-SAT for a Class of Normal Modal Logics.  Information Processing Letters 54(5), pages 281-287, 1995. ( BibTeX )

1994

• S. Demri.  Resolution for Weak Modal Logics.  In Proceedings of the 6th International Conference on Artificial Intelligence: Methodology, Systems, Applications, Sofia, Bulgaria, September 1994, pages 131-140. World Scientific, 1994. ( PS | PS.GZ | BibTeX )

About LSV

• News
• People
• Research
• Seminars
• Teaching
• Contact

• École Normale Supérieure de Cachan
• Centre National de la Recherche Scientifique