1899140
Learning Cycle-Linear Hybrid Automata for Excitable Cells
We show how to automatically learn the class of Hybrid Automata called Cycle-Linear Hybrid Automata (CLHA) in order to model the behavior of excitable cells. Such cells, whose main purpose is to amplify and propagate an electrical signal known as the action potential (AP), serve as the "biologic transistors" of living organisms. The learning algorithm we propose comprises the following three phases: (1) Geometric analysis of the APs in the training set is used to identify, for each AP, the modes and switching logic of the corresponding Linear Hybrid Automata. (2) For each mode, the modified Prony's method is used to learn the coefficients of the associated linear flows. (3) The modified Prony's method is used again to learn the functions that adjust, on a per-cycle basis, the mode dynamics and switching logic of the Linear Hybrid Automata obtained in the first two phases. Our results show that the learned CLHA is able to successfully capture AP morphology and other important excitable-cell properties, such as refractoriness and restitution, up to a prescribed approximation error. Our approach is fully implemented in MATLAB and, to the best of our knowledge, provides the most accurate approximation model for ECs to date.
2481844
Proving Atomicity: An Assertional Approach
Atomicity (or linearizability) is a commonly used consistency criterion for distributed services and objects. Although atomic object implementations are abundant, proving that algorithms achieve atomicity has turned out to be a challenging problem. In this paper, we initiate the study of systematic ways of verifying distributed implementations of atomic objects, beginning with read/write objects (registers). Our general approach is to replace the existing operational reasoning about events and partial orders with assertional reasoning about invariants and simulation relations. To this end, we define an abstract state machine that captures the atomicity property and prove correctness of the object implementations by establishing a simulation mapping between the implementation and the specification automata. We demonstrate the generality of our specification by showing that it is implemented by three different read/write register constructions: the message-passing register emulation of Attiya, Bar-Noy and Dolev, its optimized version based on real time, and the shared memory register construction of Vitanyi and Awerbuch. In addition, we show that a simplified version of our specification is implemented by a general atomic object construction based on the Lamport’s replicated state machine algorithm.
1158736
Specifying and proving properties of timed I/O automata in the TIOA toolkit
Timed I/O Automata (TIOA) is a mathematical framework for modeling and verification of distributed systems that involve discrete and continuous dynamics. TIOA can be used for example, to model a real-time software component controlling a physical process. The TIOA model is sufficiently general to subsume other models in use for timed systems. The TIOA toolkit, currently under development, is aimed at supporting system development based on TIOA specifications. The TIOA toolkit is an extension of the IOA toolkit, which provides a specification simulator, a code generator, and both model checking and theorem proving support for analyzing specifications. This paper focuses on modeling of timed systems with TIOA and the TAME-based theorem proving support provided in the toolkit, for proving system properties, including timing properties. Several examples are provided by way of illustration
29308229
Safety Verification of Model Helicopter Controller Using Hybrid Input/Output Automata
This paper presents an application of the Hybrid I/O Automaton (HIOA) framework [12] in verifying a realistic hybrid system. A supervisory pitch controller for a model helicopter system is designed and then verified. The design of the supervisor is limited by the actuator bandwidth, the sensor inaccuracies, and the sampling rates. Verification is carried out by induction over the length of an execution of the composed system automaton. The HIOA model makes the inductive proofs tractable by decomposing them into independent discrete and continuous parts. The paper also presents a set of language constructs for specifying hybrid I/O automata.
3106881
Path vector face routing: geographic routing with local face information
Existing geographic routing algorithms depend on the planarization of the network connectivity graph for correctness, and the planarization process gives rise to a well-defined notion of "faces". In this paper, we demonstrate that we can improve routing performance by storing a small amount of local face information at each node. We present a protocol, path vector exchange (PVEX), that maintains local face information at each node efficiently, and a new geographic routing algorithm, greedy path vector face routing (GPVFR), that achieves better routing performance in terms of both path stretch and hop stretch than existing geographic routing algorithms by exploiting available local face information. Our simulations demonstrate that GPVFR/PVEX achieves significantly reduced path and hop stretch than greedy perimeter stateless routing (GPSR) and somewhat better performance than greedy other adaptive face routing (GOAFR+) over a wide range of network topologies. The cost of this improved performance is a small amount of additional storage, and the bandwidth required for our algorithm is comparable to GPSR and GOAFR+ in quasi-static networks.
3477203
Fault escapes in duplex systems
Hardware duplication techniques are widely used for concurrent error detection in dependable systems to ensure high availability and data integrity. These techniques are vulnerable to common-mode failures (CMFs). Use of duplex systems with diverse implementations of the two modules has been proposed in the past for protection against CMFs. In this paper, we define a category of faults, called non-self-testable faults that undermine the data integrity of dependable systems. These faults produce identical errors at the outputs of the two modules of a duplex system and can potentially be caused by CMFs. The main contributions of this paper are: (1) techniques that identify non-self-testable faults in duplex systems, and (2) design methods that reduce the number of non-self-testable faults by test point insertion. We show that our algorithm for identifying non-self-testable faults runs orders of magnitude faster than exact techniques with minimal loss of accuracy. Also, there is a significant reduction in the number of test points required for duplex systems with diverse implementations compared to duplex systems with identical implementations. Thus, we can detect common-mode failures in diverse duplex systems using very few test points. These results are especially useful for systems with user-programmable logic elements that enhance the practicality of using diverse designs in duplex systems.
35096806
Human Face Identification from Video Based on Frequency Domain Asymmetry Representation Using Hidden Markov Models
In this paper we introduce a novel human face identification scheme from video data based on a frequency domain representation of facial asymmetry. A Hidden Markov Model (HMM) is used to learn the temporal dynamics of the training video sequences of each subject and classification of the test video sequences is performed using the likelihood scores obtained from the HMMs. We apply this method to a video database containing 55 subjects showing extreme expression variations and demonstrate that the HMM-based method performs much better than identification based on the still images using an Individual PCA (IPCA) classifier, achieving more than 30% improvement.
16142371
How To Safeguard Your Sensitive Data
In order to safeguard a sensitive database, we must ensure both its privacy and its longevity. However, privacy and longevity tend to be competing objectives. We show how to design a system that provides both good privacy and good longevity simultaneously. Systems are modelled as compositions of two basic operators, copy and split. We propose metrics with which to evaluate the privacy, longevity and performance offered by such systems. The search for the "best" system under these metrics is then formulated as a constrained optimization problem. Solving the optimization problem exactly turns out to be intractable, so we propose techniques for efficiently finding an approximate solution
11095930
II-DFT: a hybrid dft architecture for low-cost high quality structural testing
This paper describes a Hybrid DFT (H-DFT) architecture for low-cost, high quality structural testing in the high volume manufacturing (HVM) environment. This structure efficiently combines several testing and test data compression approaches to enable application of a huge amount of ATPG and Weighed Random-BIST (WR-BIST) patterns. Results obtained from the application of the H-DFT technique to industrial designs demonstrate significant savings in test cost in terms of test data volume and test application time without compromising test quality. Implementation of the HDFT architecture on Intel ASIC and microprocessor designs are described.
62742629
Local facial asymmetry for expression classification
We explore a novel application of facial asymmetry: expression classification. Using 2D facial expression images, we show the effectiveness of automatically selected local facial asymmetry for expression recognition. Quantitative evaluations of expression classification using local asymmetry demonstrate statistically significant improvements over expression classification results on the same data set without explicit representation of facial asymmetry. A comparison of discriminative local facial asymmetry features for expression classification versus human identification is given.