oalib

Publish in OALib Journal

ISSN: 2333-9721

APC: Only $99

Submit

Search Results: 1 - 10 of 1090 matches for " Stephane Demri "
All listed articles are free for downloading (OA Articles)
Page 1 /1090
Display every page Item
LTL with the Freeze Quantifier and Register Automata
Stephane Demri,Ranko Lazic
Computer Science , 2006,
Abstract: A data word is a sequence of pairs of a letter from a finite alphabet and an element from an infinite set, where the latter can only be compared for equality. To reason about data words, linear temporal logic is extended by the freeze quantifier, which stores the element at the current word position into a register, for equality comparisons deeper in the formula. By translations from the logic to alternating automata with registers and then to faulty counter automata whose counters may erroneously increase at any time, and from faulty and error-free counter automata to the logic, we obtain a complete complexity table for logical fragments defined by varying the set of temporal operators and the number of registers. In particular, the logic with future-time operators and 1 register is decidable but not primitive recursive over finite data words. Adding past-time operators or 1 more register, or switching to infinite data words, cause undecidability.
The complexity of linear-time temporal logic over the class of ordinals
Stephane Demri,Alexander Rabinovich
Computer Science , 2010, DOI: 10.2168/LMCS-6(4:9)2010
Abstract: We consider the temporal logic with since and until modalities. This temporal logic is expressively equivalent over the class of ordinals to first-order logic by Kamp's theorem. We show that it has a PSPACE-complete satisfiability problem over the class of ordinals. Among the consequences of our proof, we show that given the code of some countable ordinal alpha and a formula, we can decide in PSPACE whether the formula has a model over alpha. In order to show these results, we introduce a class of simple ordinal automata, as expressive as B\"uchi ordinal automata. The PSPACE upper bound for the satisfiability problem of the temporal logic is obtained through a reduction to the nonemptiness problem for the simple ordinal automata.
Deciding regular grammar logics with converse through first-order logic
Stephane Demri,Hans de Nivelle
Computer Science , 2003,
Abstract: We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. This translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. A consequence of the translation is that the general satisfiability problem for regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Using the same method, we show how some other modal logics can be naturally translated into GF2, including nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed point-operators.
Model checking memoryful linear-time logics over one-counter automata
Stephane Demri,Ranko Lazic,Arnaud Sangnier
Computer Science , 2008,
Abstract: We study complexity of the model-checking problems for LTL with registers (also known as freeze LTL) and for first-order logic with data equality tests over one-counter automata. We consider several classes of one-counter automata (mainly deterministic vs. nondeterministic) and several logical fragments (restriction on the number of registers or variables and on the use of propositional variables for control locations). The logics have the ability to store a counter value and to test it later against the current counter value. We show that model checking over deterministic one-counter automata is PSPACE-complete with infinite and finite accepting runs. By constrast, we prove that model checking freeze LTL in which the until operator is restricted to the eventually operator over nondeterministic one-counter automata is undecidable even if only one register is used and with no propositional variable. As a corollary of our proof, this also holds for first-order logic with data equality tests restricted to two variables. This makes a difference with the facts that several verification problems for one-counter automata are known to be decidable with relatively low complexity, and that finitary satisfiability for the two logics are decidable. Our results pave the way for model-checking memoryful (linear-time) logics over other classes of operational models, such as reversal-bounded counter machines.
Petri Net Reachability Graphs: Decidability Status of First Order Properties
Philippe Darondeau,Stephane Demri,Roland Meyer,Christophe Morvan
Computer Science , 2012, DOI: 10.2168/LMCS-8(4:9)2012
Abstract: We investigate the decidability and complexity status of model-checking problems on unlabelled reachability graphs of Petri nets by considering first-order and modal languages without labels on transitions or atomic propositions on markings. We consider several parameters to separate decidable problems from undecidable ones. Not only are we able to provide precise borders and a systematic analysis, but we also demonstrate the robustness of our proof techniques.
On Selective Unboundedness of VASS
Stéphane Demri
Electronic Proceedings in Theoretical Computer Science , 2010, DOI: 10.4204/eptcs.39.1
Abstract: Numerous properties of vector addition systems with states amount to checking the (un)boundedness of some selective feature (e.g., number of reversals, run length). Some of these features can be checked in exponential space by using Rackoff's proof or its variants, combined with Savitch's theorem. However, the question is still open for many others, e.g., reversal-boundedness. In the paper, we introduce the class of generalized unboundedness properties that can be verified in exponential space by extending Rackoff's technique, sometimes in an unorthodox way. We obtain new optimal upper bounds, for example for place-boundedness problem, reversal-boundedness detection (several variants exist), strong promptness detection problem and regularity detection. Our analysis is sufficiently refined so as we also obtain a polynomial-space bound when the dimension is fixed.
Reasoning about transfinite sequences
Stéphane Demri,David Nowak
Computer Science , 2005, DOI: 10.1142/S0129054107004589
Abstract: We introduce a family of temporal logics to specify the behavior of systems with Zeno behaviors. We extend linear-time temporal logic LTL to authorize models admitting Zeno sequences of actions and quantitative temporal operators indexed by ordinals replace the standard next-time and until future-time operators. Our aim is to control such systems by designing controllers that safely work on $\omega$-sequences but interact synchronously with the system in order to restrict their behaviors. We show that the satisfiability problem for the logics working on $\omega^k$-sequences is EXPSPACE-complete when the integers are represented in binary, and PSPACE-complete with a unary representation. To do so, we substantially extend standard results about LTL by introducing a new class of succinct ordinal automata that can encode the interaction between the different quantitative temporal operators.
A Note on the Complexity of Model-Checking Bounded Multi-Pushdown Systems
Kshitij Bansal,Stéphane Demri
Computer Science , 2012,
Abstract: In this note, we provide complexity characterizations of model checking multi-pushdown systems. Multi-pushdown systems model recursive concurrent programs in which any sequential process has a finite control. We consider three standard notions for boundedness: context boundedness, phase boundedness and stack ordering. The logical formalism is a linear-time temporal logic extending well-known logic CaRet but dedicated to multi-pushdown systems in which abstract operators (related to calls and returns) such as those for next-time and until are parameterized by stacks. We show that the problem is EXPTIME-complete for context-bounded runs and unary encoding of the number of context switches; we also prove that the problem is 2EXPTIME-complete for phase-bounded runs and unary encoding of the number of phase switches. In both cases, the value k is given as an input (whence it is not a constant of the model-checking problem), which makes a substantial difference in the complexity. In certain cases, our results improve previous complexity results.
On the freeze quantifier in Constraint LTL: decidability and complexity
Stéphane Demri,Ranko Lazic,David Nowak
Computer Science , 2006, DOI: 10.1016/j.ic.2006.08.003
Abstract: Constraint LTL, a generalisation of LTL over Presburger constraints, is often used as a formal language to specify the behavior of operational models with constraints. The freeze quantifier can be part of the language, as in some real-time logics, but this variable-binding mechanism is quite general and ubiquitous in many logical languages (first-order temporal logics, hybrid logics, logics for sequence diagrams, navigation logics, logics with lambda-abstraction etc.). We show that Constraint LTL over the simple domain (N,=) augmented with the freeze quantifier is undecidable which is a surprising result in view of the poor language for constraints (only equality tests). Many versions of freeze-free Constraint LTL are decidable over domains with qualitative predicates and our undecidability result actually establishes Sigma_1^1-completeness. On the positive side, we provide complexity results when the domain is finite (EXPSPACE-completeness) or when the formulae are flat in a sense introduced in the paper. Our undecidability results are sharp (i.e. with restrictions on the number of variables) and all our complexity characterisations ensure completeness with respect to some complexity class (mainly PSPACE and EXPSPACE).
Shipping and Invasion of Second-Hand Vehicles in West African Ports: Analysing the Factors and Market Effects at the Port of Abidjan  [PDF]
Nomel Paul Stephane Essoh
American Journal of Industrial and Business Management (AJIBM) , 2013, DOI: 10.4236/ajibm.2013.32026
Abstract:

Since more than a decade sub-Saharan Africa has known a plenty of second-hands vehicles especially in francophone West Africa. These second hand vehicles made of personal fleet of cars constitute more than the 85% of the total number of automobiles in the region. That has contributed in a paradox way to businesses creation and increased the level of entrepreneurship in the automobile sector while it has been a help in performing the taxes collection and policy in ports. The invasion of these types of cars has led to West African ports cities especially Abidjan in Cote dIvoire to increase the demand. This paper tends to show the shipping practices of the second hand cars and the demand drawn by the socioeconomic environment. It illustrates the effects on port of Abidjan in Cote dIvoire with the local institutional and regulatory function in the shipping activities of the second hand cars. And so far, this study examines the evidence of how the invasion is organized since its import origins and zones to the sales stations and finally describe how this industry generates income for both public sector and private business owners.

Page 1 /1090
Display every page Item


Home
Copyright © 2008-2017 Open Access Library. All rights reserved.