On projective and separable properties
Lecture notes in computer sciencePublished 22 November 2005
Doron Peled
Citations4
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
A language L over the Cartesian product of component alphabets is called projective if it is closed under projections. That is, together with each word α ε L, it contains all the words that have the same projections up to stuttering as α. We prove that in each of the behavior classes: ω-regular, regular and star-free ω-regular (i.e., definable by linear temporal logic) languages, the projective languages are precisely the Boolean combinations of stuttering-closed component languages from the corresponding class. Languages of these behavior classes can also be seen as properties of various temporal logics; some uses of projective properties for specification and verification of programs are studied.
Keywords
Computer Science
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Communications of the ACMTime, clocks, and the ordering of events in a distributed system
8,437 Citations1978Leslie Lamport
A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events, and a bound is derived on how far out of synchrony the clocks can become.
IEEE Transactions on ComputersHow to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
2,503 Citations1979Lamport
Many large sequential computers execute operations in a different order than is specified by the program, and a correct execution by each processor does not guarantee the correct execution of the entire program.
Journal of the ACMThe complexity of propositional linear temporal logics
1,107 Citations1985A. Prasad Sistla, E. M. Clarke
The complexity of satisfiability and determination of truth in a particular finite structure are considered for different propositional linear temporal logics and it is shown that these problems are NP-complete for the logic with F and PSPACE- complete for the logics with F, X, with U, with S, X operators.
Elsevier eBooksAutomata on Infinite Objects
947 Citations1990Wolfgang Thomas
This chapter discusses the formulation of two interesting generalizations of Rabin's Tree Theorem and presents some remarks on the undecidable extensions of the monadic theory of the binary tree.
On the temporal analysis of fairness
726 Citations1980Dov M. Gabbay, Amir Pnueli +2 more
It is shown that with the addition of the 'until' operator -U the temporal language becomes expressively complete and two deductive systems DX and DUX are proved to be complete for the languages without and with the new operator respectively.
Medical Entomology and ZoologyCounter-Free Automata
721 Citations1971Robert McNaughton, Seymour Papert
A particular class of finite-state automata, christened by the authors "counter-free," is shown here to behave like a good actor: it can drape itself so thoroughly in the notational guise and embed itself so deeply in the conceptual character of several quite different approaches to automata theory that on the surface it is hard to believe that all these roles are being assumed by the same class.
Checking that finite state concurrent programs satisfy their linear specification
618 Citations1985Orna Lichtenstein, Amir Pnueli
An algorithm for checking satisfiability of a linear time temporal logic formula over a finite state concurrent program and a formal proof in case the formula is valid over the program is presented.
Lecture notes in computer scienceAll from one, one for all: on model checking using representatives
521 Citations1993Doron Peled
An algorithm for constructing a state graph that contains at least one representative sequence for each equivalence class, and a formula rewriting technique is presented to allow coarser equivalence relation among sequences, such that less representatives are needed.
The theory of database concurrency control
448 Citations1986Christos H. Papadimitriou
The theory of database concurrency control is one book that the authors really recommend you to read, to get more solutions in solving this problem.
IFIP CongressWhat Good is Temporal Logic
444 Citations1983Leslie Lamport
This was an invited paper and describes the state of my views on specification and verification at the time, notable for introducing the idea of invariance under stuttering and explaining why it’s a vital attribute of a specification logic.
Lecture notes in computer scienceRealizable and unrealizable specifications of reactive systems
243 Citations1989Martı́n Abadi, Leslie Lamport +1 more
A class of realizable specifications is defined, which includes all specifications that can be implemented by physically possible systems, but also some that have no real implementations for reasons that do not concern us.
Theoretical Computer ScienceComplexity of some problems in Petri nets
238 Citations1977Neil D. Jones, Lawrence H. Landweber +1 more
The problem of deciding whether a Petri net is persistent is reducible to reachability, partially answering a question of Keller, and it is shown that the controllability problem requires exponential space, even for 1-bounded nets.
Distributed ComputingAppraising fairness in languages for distributed programming
153 Citations1988Krzysztof R. Apt, Nissim Francez +1 more
The relations among various languages and models for distributed computation and various possible definitions of fairness are considered, and natural semantic criteria are presented which an acceptable notion of fairness should satisfy.
ACM Transactions on Programming Languages and SystemsLazy caching
129 Citations1993Yehuda Afek, Geoffrey Brown +1 more
An algorithm is presented that exploits a weaker condition than is normally implemented to achieve greater concurrency and is shown to satisfy the weak consistency condition.
Theoretical Computer ScienceA syntactic congruence for rational ω-languages
78 Citations1985André Arnold
The syntactic congruence of L is defined, which is the largest congruences having this property, and it is shown that if L is a rational ω-language, then there exists a finite congruency for which L is saturated in the following sense.
Distributed ComputingVerification of distributed programs using representative interleaving sequences
74 Citations1992Shmuel Katz, Doron Peled
A formal proof method for distributed programs that explicitly identifies equivalence classes of execution sequences which are equivalent up to permuting commutative operations using the temporal logic ISTL.
International Journal of Algebra and ComputationAN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
66 Citations1993Thomas Wilke
An algebraic approach to the theory of regular languages of finite and infinite words (∞-languages) is presented and a variety theorem is proved: there is a one-to-one correspondence between varieties of ∞-Languages and pseudovarieties of right binoids.
Formal Aspects of ComputingEvent fairness and non-interleaving concurrency
42 Citations1989Marta Kwiatkowska
A class of generalised notions of (weak, strong and unconditional) event fairness relative to progress requirements is derived and the weakest fairness notion in this class is shown to coincide with maximality with respect to the partial order over traces.
OPAL (Open@LaTrobe) (La Trobe University)Fairness for non-interleaving concurrency
33 Citations1989Marta Kwiatkowska
A topological characterization of behavioural properties which includes safety, progress and fairness properties has been provided in a non-interleaving semantic model for concurrency.
Specifying and proving serializability in temporal logic
18 Citations2002Doron Peled, Shmuel Katz +1 more
A formal verification system for serializability that uses classical logic reasoning is provided and Serializability for the multiversion-timestamp algorithm is verified.
Lecture notes in computer scienceInterleaving set temporal logic
8 Citations1989Shmuel Katz, Doron Peled