|
Partial Order Reduction
In computer science, partial order reduction is a technique for reducing the size of the state-space to be searched by a model checking or automated planning and scheduling algorithm. It exploits the commutativity of concurrently executed transitions that result in the same state when executed in different orders. In explicit state space exploration, partial order reduction usually refers to the specific technique of expanding a representative subset of all enabled transitions. This technique has also been described as model checking with representatives. There are various versions of the method, the so-called stubborn set method, ample set method, and persistent set method. Ample sets Ample sets are an example of model checking with representatives. Their formulation relies on a separate notion of ''dependency''. Two transitions are considered independent only if whenever they are mutually enabled, they cannot disable another and the execution of both results in a unique state r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical disciplines (including the design and implementation of Computer architecture, hardware and Computer programming, software). Computer science is generally considered an area of research, academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing Vulnerability (computing), security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Progr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
State Transition System
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a singleton, the system is essentially unlabeled, and a simpler definition that omits the labels is possible. Transition systems coincide mathematically with abstract rewriting systems (as explained further in this article) and directed graphs. They differ from finite-state automata in several ways: * The set of states is not necessarily finite, or even countable. * The set of transitions is not necessarily finite, or even countable. * No "start" state or "final" states are given. Transition systems can be represented as directed graphs. Formal definition Formally, a transition system is a pair (S, \rightarrow) where S is a set of st ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Model Checking
In computer science, model checking or property checking is a method for checking whether a finite-state model of a system meets a given specification (also known as correctness). This is typically associated with hardware or software systems, where the specification contains liveness requirements (such as avoidance of livelock) as well as safety requirements (such as avoidance of states representing a system crash). In order to solve such a problem algorithmically, both the model of the system and its specification are formulated in some precise mathematical language. To this end, the problem is formulated as a task in logic, namely to check whether a structure satisfies a given logical formula. This general concept applies to many kinds of logic and many kinds of structures. A simple model-checking problem consists of verifying whether a formula in the propositional logic is satisfied by a given structure. Overview Property checking is used for verification when two desc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Automated Planning And Scheduling
Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines. Automation has been achieved by various means including Mechanical system, mechanical, hydraulic, pneumatic, electrical, electronic devices, and computers, usually in combination. Complicated systems, such as modern factories, airplanes, and ships typically use combinations of all of these techniques. The benefit of automation includes labor savings, reducing waste, savings in electricity costs, savings in material costs, and improvements to quality, accuracy, and precision. Automation includes the use of various equipment and control systems such as machinery, processes in factories, boilers, and heat-treating ovens, switching on telephone networks, steering, and stabilization of ships, aircraft, and other applications and vehicles with ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can perform automated deductions (referred to as automated reasoning) and use mathematical and logical tests to divert the code execution through various routes (referred to as automated decision-making). Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus". In contrast, a Heuristic (computer science), heuristic is an approach to problem solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. As an effective method, an algorithm ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Transition (computer Science)
Transition refers to a computer science paradigm in the context of communication systems which describes the change of communication mechanisms, i.e., functions of a communication system, in particular, service and Communications protocol, protocol components. In a transition, communication mechanisms within a system are replaced by functionally comparable mechanisms with the aim to ensure the highest possible quality, e.g., as captured by the quality of service. Transitions enable communication systems to adapt to changing conditions during runtime. This change in conditions can, for example, be a rapid increase in the load on a certain service that may be caused, e.g., by large gatherings of people with mobile devices. A transition often impacts multiple mechanisms at different communication layers of a OSI model, layered architecture. Mechanisms are given as conceptual elements of a networked communication system and are linked to specific functional units, for example, as a se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Static Analysis
Static analysis, static projection, or static scoring is a simplified analysis wherein the effect of an immediate change to a system is calculated without regard to the longer-term response of the system to that change. If the short-term effect is then extrapolated to the long term, such extrapolation is inappropriate. Its opposite, dynamic analysis or dynamic scoring, is an attempt to take into account how the system is likely to respond to the change over time. One common use of these terms is budget policy in the United States, although it also occurs in many other statistical disputes. Examples A famous example of extrapolation of static analysis comes from overpopulation theory. Starting with Thomas Malthus at the end of the 18th century, various commentators have projected some short-term population growth trend for years into the future, resulting in the prediction that there would be disastrous overpopulation within a generation or two. Malthus himself essentially cla ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Temporal Logic
In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths, e.g., a condition will eventually be true, a condition will be true until another fact becomes true, etc. It is a fragment of the more complex CTL*, which additionally allows branching time and quantifiers. Subsequently, LTL is sometimes called ''propositional temporal logic'', abbreviated ''PTL''. In terms of expressive power, linear temporal logic (LTL) is a fragment of first-order logic. LTL was first proposed for the formal verification of computer programs by Amir Pnueli in 1977. Syntax LTL is built up from a finite set of propositional variables ''AP'', the logical operators ¬ and ∨, and the temporal modal operators X (some literature uses O or N) and U. Formally, the set of LTL formulas over ''AP'' is inductively defined as follows: * if p ∈ ''AP'' then p is an LTL formula; * if Ï ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cycle (sequence)
In mathematics, a periodic sequence (sometimes called a cycle) is a sequence for which the same terms are repeated over and over: :''a''1, ''a''2, ..., ''a''''p'', ''a''1, ''a''2, ..., ''a''''p'', ''a''1, ''a''2, ..., ''a''''p'', ... The number ''p'' of repeated terms is called the period (period). Definition A (purely) periodic sequence (with period ''p''), or a ''p-''periodic sequence, is a sequence ''a''1, ''a''2, ''a''3, ... satisfying :''a''''n''+''p'' = ''a''''n'' for all values of ''n''. If a sequence is regarded as a function whose domain is the set of natural numbers, then a periodic sequence is simply a special type of periodic function. The smallest ''p'' for which a periodic sequence is ''p''-periodic is called its least period or exact period. Examples Every constant function is 1-periodic. The sequence 1,2,1,2,1,2\dots is periodic with least period 2. The sequence of digits in the decimal expansion of 1/7 is periodic with period 6: :\frac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deadlocks
In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock. Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, because in these contexts systems often use software or hardware locks to arbitrate shared resources and implement process synchronization. In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process. If a process remains indefinitely unable to change its state because resources requested by it are being used by another process that itself is waiting, then the system is said to be in a deadlock. In a communications system, deadlocks occur mainly due to los ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
POPL
The annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) is an academic conference in the field of computer science, with focus on fundamental principles in the design, definition, analysis, and implementation of programming languages, programming systems, and programming interfaces. The venue is jointly sponsored by two Special Interest Groups of the Association for Computing Machinery: SIGPLAN and SIGACT. POPL ranks as A* (top 4%) in the CORE conference ranking. The proceedings of the conference are hosted at the ACM Digital Library. They were initially under a paywall, but since 2017 they are published in open access as part of the journal ''Proceedings of the ACM on Programming Languages'' (PACMPL). Affiliated events * Declarative Aspects of Multicore Programming (DAMP) * Foundations and Developments of Object-Oriented Languages (FOOL/WOOD) * Partial Evaluation and Semantics-Based Program Manipulation (PEPM) * Practical Applications of Decl ... [...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] |
.jpg "Click for more on -> Model Checking")
