|
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 P ... [...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 with close connections to cognitive science and mathematical logic. 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 ... [...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 ... [...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 infinite ordinal number, modeling a 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
ω-automaton
In automata theory, a branch of theoretical computer science, an Ordinal number, ω-automaton (or stream automaton) is a variation of a finite automaton 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 automaton, Büchi automata, Rabin automata, Streett automata, parity automata and Muller automaton, Muller automata, each deterministic or non-deterministic. T ... [...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 S is called finite if there exists a bijection for some natural number n (natural numbers are defined as sets in Zermelo-Fraenkel set theory). The number n ... [...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 image:Maurice Vincent Wilkes 1980 (3).jpg, Sir Maurice Wilkes served as the first President of BCS in 1957. The British Computer Society (BCS), branded BCS, The Chartered Institute for IT, since 2009, is a professional body and a learned ... References External links * Academic journals established in 1973 Computer science books Series of non-fiction books ... [...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. Among the important results originally published in CAV are techniques in model checking, such as Counterexample-Guided Abstraction Refinement and partial order reduction. It is often ranked among the top conferences in computer science. The first CAV was held in 1989 in Grenoble, France. The CAV proceedings (1989-present) are published by Springer Science+Business Media. They have been open access since 2018. The annual CAV Award was established in 2008. The list of recipients and citations can be found at https://i-cav.org/cav-award/. See also * List of computer science conferences * Symposium on Logic in Computer Science * European Joint Conferences on Theory and Practice of Software References External links *bibliograp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Amir Pnueli
Amir Pnueli (; 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 Science Department of New York ... [...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 (), or ULiège, is a major public university of the French Community of Belgium founded in 1817 and based in Liège, Wallonia, Belgium. Its official language is French (language), French. History The university was foun .... [...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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Moshe Vardi
Moshe Ya'akov Vardi () is an Israeli theoretical computer scientist. He is the Karen Ostrum George Distinguished Service Professor in Computational Engineering at Rice University, United States. and a faculty advisor for the Ken Kennedy Institute. His interests focus on applications of logic to computer science, including database theory, finite model theory, knowledge of multi-agent systems, computer-aided verification and reasoning, and teaching logic across the curriculum. He is an expert in model checking, constraint satisfaction and database theory, common knowledge (logic), and theoretical computer science. Vardi has authored or co-authored over 700 technical papers as well as editing several collections. He has authored the books ''Reasoning About Knowledge'' with Ronald Fagin, Joseph Halpern, and Yoram Moses, and ''Finite Model Theory and Its Applications'' with Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Yde Venema, and Scott Weins ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Temporal Logic To Büchi Automaton
In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a ''function'' (or '' mapping''); * linearity of a ''polynomial''. An example of a linear function is the function defined by f(x)=(ax,bx) that maps the real line to a line in the Euclidean plane R2 that passes through the origin. An example of a linear polynomial in the variables X, Y and Z is aX+bY+cZ+d. Linearity of a mapping is closely related to '' proportionality''. Examples in physics include the linear relationship of voltage and current in an electrical conductor (Ohm's law), and the relationship of mass and weight. By contrast, more complicated relationships, such as between velocity and kinetic energy, are ''nonlinear''. Generalized for functions in more than one dimension, linearity means the property of a function of being compatible with addition and scaling, also known as the superposition principle. Linearity of a polynomial means that its degree is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
