|
Hybrid Automaton
In automata theory, a hybrid automaton (plural: ''hybrid automata'' or ''hybrid automatons'') is a mathematical model for precisely describing hybrid systems, for instance systems in which digital computational processes interact with analog physical processes. A hybrid automaton is a finite state machine with a finite set of continuous variables whose values are described by a set of ordinary differential equations. This combined specification of discrete and continuous behaviors enables dynamic systems that comprise both digital and analog components to be modeled and analyzed. Examples A simple example is a room-thermostat-heater system where the temperature of the room evolves according to laws of thermodynamics and the state of the heater (on/off); the thermostat senses the temperature, performs certain computations and turns the heater on and off. In general, hybrid automata have been used to model and analyze a variety of embedded systems including vehicle control systems, air ... [...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] |
Labeled Multidigraph
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. There are two distinct notions of multiple edges: * ''Edges without own identity'': The identity of an edge is defined solely by the two nodes it connects. In this case, the term "multiple edges" means that the same edge can occur several times between these two nodes. * ''Edges with own identity'': Edges are primitive entities just like nodes. When multiple edges connect two nodes, these are different edges. A multigraph is different from a hypergraph, which is a graph in which an edge can connect any number of nodes, not just two. For some authors, the terms ''pseudograph'' and ''multigraph'' are synonymous. For others, a pseudograph is a multigraph that is permitted to have loops. Undirected multigraph (edges without ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nancy Lynch
Nancy Ann Lynch (born January 19, 1948) is a mathematician, a theorist, and a professor at the Massachusetts Institute of Technology. She is the NEC Professor of Software Science and Engineering in the EECS department and heads the "Theory of Distributed Systems" research group at MIT's Computer Science and Artificial Intelligence Laboratory. Education and early life Lynch was born in Brooklyn, and her academic training was in mathematics. She attended Brooklyn College and MIT, where she received her Ph.D. in 1972 under the supervision of Albert R. Meyer. Work She served on the math and computer science faculty at several other universities, including Tufts University, the University of Southern California, Florida International University, and the Georgia Institute of Technology (Georgia Tech), prior to joining the MIT faculty in 1982. Since then, she has been working on applying mathematics to the tasks of understanding and constructing complex distributed systems. Her 1985 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rajeev Alur
Rajeev Alur is an American professor of computer science at the University of Pennsylvania who has made contributions to formal methods, programming languages, and automata theory, including notably the introduction of timed automata (Alur and Dill, 1994) and nested words (Alur and Madhusudan, 2004). Prof. Alur was born in Pune. He obtained his bachelor's degree in computer science from the Indian Institute of Technology at Kanpur, India, in 1987, and Ph.D. in computer science from Stanford University, California, USA, in 1991. Before joining the University of Pennsylvania in 1997, he was with the Computing Science Research Center at Bell Laboratories. His research has included formal modeling and analysis of reactive systems, hybrid systems, model checking, software verification, design automation for embedded software, and program synthesis. He is a Fellow of the ACM, a Fellow of the IEEE, and has served as the chair of ACM SIGBED (Special Interest Group on Embedded Systems) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Signal Automaton
In automata theory, a field of computer science, a signal automaton is a finite automaton extended with a finite set of real-valued clocks. During a run of a signal automaton, clock values increase all with the same speed. Along the transitions of the automaton, clock values can be compared to integers. These comparisons form guards that may enable or disable transitions and by doing so constrain the possible behaviors of the automaton. Further, clocks can be reset. Example Before formally defining what a signal automaton is, an example will be given. Let one consider the language \mathcal L of signals, over a binary alphabet \, which contains signals \gamma such that: * A appears in singular intervals. That is, the set of times \ is discrete, and * A appears at least once during each interval of length one. This language can be accepted by the automaton pictured nearby. As for finite automaton, incoming arrows represents initial locations and double circle represents accepting l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Timed Automaton
In automata theory, a timed automaton is a finite automaton extended with a finite set of real-valued clocks. During a run of a timed automaton, clock values increase all with the same speed. Along the transitions of the automaton, clock values can be compared to integers. These comparisons form guards that may enable or disable transitions and by doing so constrain the possible behaviors of the automaton. Further, clocks can be reset. Timed automata are a sub-class of a type hybrid automata. Timed automata can be used to model and analyse the timing behavior of computer systems, e.g., real-time systems or networks. Methods for checking both safety and liveness properties have been developed and intensively studied over the last 20 years. It has been shown that the state reachability problem for timed automata is decidable,Rajeev Alur, David L. Dill. 199A Theory of Timed Automata In Theoretical Computer Science, vol. 126, 183–235, pp. 194–1955 which makes this an interesting su ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Timed Automaton
In automata theory, a timed automaton is a finite automaton extended with a finite set of real-valued clocks. During a run of a timed automaton, clock values increase all with the same speed. Along the transitions of the automaton, clock values can be compared to integers. These comparisons form guards that may enable or disable transitions and by doing so constrain the possible behaviors of the automaton. Further, clocks can be reset. Timed automata are a sub-class of a type hybrid automata. Timed automata can be used to model and analyse the timing behavior of computer systems, e.g., real-time systems or networks. Methods for checking both safety and liveness properties have been developed and intensively studied over the last 20 years. It has been shown that the state reachability problem for timed automata is decidable,Rajeev Alur, David L. Dill. 199A Theory of Timed Automata In Theoretical Computer Science, vol. 126, 183–235, pp. 194–1955 which makes this an interesting su ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Counter Machine
A counter machine is an abstract machine used in a formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded ''registers'', each of which can hold a single non-negative integer, and a list of (usually sequential) arithmetic and control instructions for the machine to follow. The counter machine is typically used in the process of designing parallel algorithms in relation to the mutual exclusion principle. When used in this manner, the counter machine is used to model the discrete time-steps of a computational system in relation to memory accesses. By modeling computations in relation to the memory accesses for each respective computational step, parallel algorithms may be designed in such a matter to avoid interlocking, the simultaneous writing operation by two (or more) threads to the same memory address. Basic features For a given counter machin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reachability
In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s and ends with t. In an undirected graph, reachability between all pairs of vertices can be determined by identifying the connected components of the graph. Any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component; therefore, in such a graph, reachability is symmetric (s reaches t iff t reaches s). The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a directed graph (which, incidentally, need not be symmetric). Definition For a directed graph G = (V, E), with vertex set V and edge set E, the reachability relation of G is the transitive closure ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lazy Linear Hybrid Automaton
Lazy linear hybrid automata model the discrete time behavior of control systems containing finite-precision sensors and actuators interacting with their environment under bounded inertial delays. The model permits only linear flow constraints but the invariants and guards can be any computable function. This computational model was proposed by Manindra Agrawal and P. S. Thiagarajan. This model is more realistic and also computationally amenable than the currently popular modeling paradigm of linear hybrid automaton In automata theory, a hybrid automaton (plural: ''hybrid automata'' or ''hybrid automatons'') is a mathematical model for precisely describing hybrid systems, for instance systems in which digital computational processes interact with analog physica .... External links Formalization and theory behind the modelReachability Analysis of Lazy Linear Hybrid Automata Research{{tech-stub Automata (computation) Models of computation ... [...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] |
Multidigraph
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. There are two distinct notions of multiple edges: * ''Edges without own identity'': The identity of an edge is defined solely by the two nodes it connects. In this case, the term "multiple edges" means that the same edge can occur several times between these two nodes. * ''Edges with own identity'': Edges are primitive entities just like nodes. When multiple edges connect two nodes, these are different edges. A multigraph is different from a hypergraph, which is a graph in which an edge can connect any number of nodes, not just two. For some authors, the terms ''pseudograph'' and ''multigraph'' are synonymous. For others, a pseudograph is a multigraph that is permitted to have loops. Undirected multigraph (edges withou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Model Checking")