|
Generalized Büchi Automaton
In automata theory, a generalized Büchi automaton is a variant of a Büchi automaton. The difference with the Büchi automaton is the accepting condition, which is determined by a set of sets of states. A run is accepted by the automaton if it visits at least one state of every set of the accepting condition infinitely often. Generalized Büchi automata are equivalent in expressive power to Büchi automata; a transformation is given here. In formal verification, the model checking method needs to obtain an automaton from a LTL formula that specifies the desired program property. There are algorithms that translate a LTL formula into a generalized Büchi automaton. M. Y. Vardi and P. Wolper, Reasoning about infinite computations, Information and Computation, 115(1994), 1–37. Y. Kesten, Z. Manna, H. McGuire, A. Pnueli, A decision algorithm for full propositional temporal logic, CAV’93, Elounda, Greece, LNCS 697, Springer–Verlag, 97-109. R. Gerth, D. Peled, M.Y. Vardi and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Automata Theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function, which takes the previous state and current input symbol as its arguments. Automata theo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Information And Computation
''Information and Computation'' is a closed-access computer science journal published by Elsevier (formerly Academic Press). The journal was founded in 1957 under its former name ''Information and Control'' and given its current title in 1987. , the current editor-in-chief is David Peleg. The journal publishes 12 issues a year. History ''Information and Computation'' was founded as ''Information and Control'' in 1957 at the initiative of Leon Brillouin and under the editorship of Leon Brillouin, Colin Cherry and Peter Elias. Murray Eden joined as editor in 1962 and became sole editor-in-chief in 1967. He was succeeded by Albert R. Meyer in 1981, under whose editorship the journal was rebranded ''Information and Computation'' in 1987 in response to the shifted focus of the journal towards theory of computation and away from control theory. In 2020, Albert Mayer was succeeded by David Peleg as editor-in-chief of the journal. Indexing All articles from the ''Information and C ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
ω-language
In formal language theory within theoretical computer science, an infinite word is an infinite-length sequence (specifically, an ω-length sequence) of symbols, and an ω-language is a set of infinite words. Here, ω refers to the first ordinal number, the set of natural numbers. Formal definition Let Σ be a set of symbols (not necessarily finite). Following the standard definition from formal language theory, Σ* is the set of all ''finite'' words over Σ. Every finite word has a length, which is a natural number. Given a word ''w'' of length ''n'', ''w'' can be viewed as a function from the set → Σ, with the value at ''i'' giving the symbol at position ''i''. The infinite words, or ω-words, can likewise be viewed as functions from \mathbb to Σ. The set of all infinite words over Σ is denoted Σω. The set of all finite ''and'' infinite words over Σ is sometimes written Σ∞ or Σ≤ω. Thus an ω-language ''L'' over Σ is a subset of Σω. Operations Some common ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
ω-automaton
In automata theory, a branch of theoretical computer science, an ω-automaton (or stream automaton) is a variation of finite automata that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states. ω-automata are useful for specifying behavior of systems that are not expected to terminate, such as hardware, operating systems and control systems. For such systems, one may want to specify a property such as "for every request, an acknowledge eventually follows", or its negation "there is a request that is not followed by an acknowledge". The former is a property of infinite words: one cannot say of a finite sequence that it satisfies this property. Classes of ω-automata include the Büchi automata, Rabin automata, Streett automata, parity automata and Muller automata, each deterministic or non-deterministic. These classes of ω-automata differ only in terms of a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Finite Set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. The number of elements of a finite set is a natural number (possibly zero) and is called the ''cardinality (or the cardinal number)'' of the set. A set that is not a finite set is called an '' infinite set''. For example, the set of all positive integers is infinite: :\. Finite sets are particularly important in combinatorics, the mathematical study of counting. Many arguments involving finite sets rely on the pigeonhole principle, which states that there cannot exist an injective function from a larger finite set to a smaller finite set. Definition and terminology Formally, a set is called finite if there exists a bijection :f\colon S\to\ for some natural number . The number is the set's cardinality, denoted as . The empty set o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
LNCS
''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorials, state-of-the-art surveys, and "hot topics" are increasingly being included. The series is indexed by DBLP. See also *''Monographiae Biologicae'', another monograph series published by Springer Science+Business Media *''Lecture Notes in Physics'' *''Lecture Notes in Mathematics'' *''Electronic Workshops in Computing'', published by the British Computer Society Sir Maurice Wilkes served as the first President of BCS in 1957 BCS, The Chartered Institute for IT, known as the British Computer Society until 2009, is a professional body and a learned society that represents those working in inf ... References External links * Publications established in 1973 Computer science books Series of non-fiction books Springer S ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Aided Verification
In computer science, the International Conference on Computer-Aided Verification (CAV) is an annual academic conference on the theory and practice of computer-aided formal analysis of software and hardware systems, broadly known as formal methods. It is one of the highest-ranked conferences in computer science. Among the important results originally published in CAV are breakthrough techniques in model checking, such as Counterexample-Guided Abstraction Refinement (CEGAR) and partial order reduction. The first CAV was held in 1989 in Grenoble, France. The CAV proceedings (1989-present) are published by Springer Science+Business Media and are open access. See also * List of computer science conferences * Symposium on Logic in Computer Science * European Joint Conferences on Theory and Practice of Software External links *bibliography for CAVat DBLP DBLP is a computer science bibliography website. Starting in 1993 at Universität Trier in Germany, it grew from a small co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Amir Pnueli
Amir Pnueli ( he, אמיר פנואלי; April 22, 1941 – November 2, 2009) was an Israeli computer scientist and the 1996 Turing Award recipient. Biography Pnueli was born in Nahalal, in the British Mandate of Palestine (now in Israel) and received a Bachelor's degree in mathematics from the Technion in Haifa, and Ph.D. in applied mathematics from the Weizmann Institute of Science (1967). His thesis was on the topic of "Calculation of Tides in the Ocean". He switched to computer science during a stint as a post-doctoral fellow at Stanford University. His works in computer science focused on temporal logic and model checking, particularly regarding fairness properties of concurrent systems.. He returned to Israel as a researcher; he was the founder and first chair of the computer science department at Tel Aviv University. He became a professor of computer science at the Weizmann Institute in 1981. From 1999 until his death, Pnueli also held a position at the Computer Sc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pierre Wolper
Pierre Wolper is a Belgian computer scientist at the University of Liège. His research interests include verification methods for reactive and concurrent programs, as well as temporal databases. He is the co-recipient of the 2000 Gödel Prize, along with Moshe Y. Vardi, for his work on temporal logic with finite automata. He also received the 2005 Paris Kanellakis Award for this work. Following elections of October 2018, he becomes Rector of the University of Liège The University of Liège (french: Université de Liège), or ULiège, is a major public university of the French Community of Belgium based in Liège, Wallonia, Belgium. Its official language is French. As of 2020, ULiège is ranked in the .... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Büchi Automaton
In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machine should move to from its current state when it reads the next input character. Some states are accepting states and one state is the start state. The machine accepts an input if and only if it will pass through an accepting state infinitely many times as it reads the input. A non-deterministic Büchi automaton, later referred to just as a Büchi automaton, has a transition function which may have multiple outputs, leading to many possible paths for the same input; it accepts an infinite input if and only if some possible path is accepting. Deterministic and non-deterministic Büchi automata generalize deterministic finite automata and nondeterministic finite automata to infinite inputs. Each are types of ω-automata. Büchi automata r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Moshe Vardi
, honorific_suffix = , image = Moshe Vardi IMG 0010.jpg , birth_date = , birth_place = Israel , workplaces = Rice UniversityIBM Research Stanford University , alma_mater = , thesis_title = The Implication Problem for Data Dependencies in the Relational Model , thesis_url = , thesis_year = 1981 , doctoral_advisor = Catriel Beeri , doctoral_students = Kristin Yvonne Rozier , fields = Logic Computation , awards = , website = Moshe Ya'akov Vardi ( he, משה יעקב ורדי) is an Israeli mathematician and computer scientist. He is a Professor of Computer Science at Rice University, United States. He is University Professor, the Karen Ostrum George Professor in Computational Engineering, Distinguished Service Professor, and director of the Ken Kennedy Institute for Information Technology. His interests focus on applications of logic to computer science, including database theory, finite mo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Temporal Logic To Büchi Automaton
In formal verification, finite state model checking needs to find a Büchi automaton (BA) equivalent to a given linear temporal logic (LTL) formula, i.e., such that the LTL formula and the BA recognize the same ω-language. There are algorithms that translate an LTL formula to a BA.M.Y. Vardi and P. Wolper, Reasoning about infinite computations, Information and Computation, 115(1994), 1–37.Y. Kesten, Z. Manna, H. McGuire, A. Pnueli, A decision algorithm for full propositional temporal logic, CAV’93, Elounda, Greece, LNCS 697, Springer–Verlag, 97-109.R. Gerth, D. Peled, M.Y. Vardi and P. Wolper, "Simple On-The-Fly Automatic Verification of Linear Temporal Logic," Proc. IFIP/WG6.1 Symp. Protocol Specification, Testing, and Verification (PSTV95), pp. 3-18,Warsaw, Poland, Chapman & Hall, June 1995. P. Gastin and D. Oddoux, Fast LTL to Büchi automata translation, Thirteenth Conference on Computer Aided Verification (CAV ′01), number 2102 in LNCS, Springer-Verlag (2001), pp. 53 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
