Exploring structural symmetry automatically in symbolic trajectory evaluation

This paper presents a formal theory to characterize symmetry in netlists and symmetry in properties. The inherent correlation between the two types of symmetry is formalized as a theorem, which provides the soundness of our symmetry reduction method. A practical tactic is introduced to effectively integrate the symmetry reduction approach in a hybrid verification environment which combines theorem proving and symbolic trajectory evaluation. Finally, the effecitveness of the symmetry reduction method is demonstrated by case studies.     

Symbolic control of linear systems based on symbolic subsystems

This paper describes an approach to the control of continuous systems through the use of symbolic models describing the system behavior only at a finite number of points in the state space. These symbolic models can be seen as abstract representations of the continuous dynamics enabling the use of algorithmic controller design methods. We identify a class of linear control systems for which the loss of information incurred by working with symbolic subsystems can be compensated by feedback. We also show how to transform symbolic controllers designed for a symbolic subsystem into controllers for the original system. The resulting controllers combine symbolic controller dynamics with continuous feedback control laws and can thus be seen as hybrid systems. Furthermore, if the symbolic controller already accounts for software/hardware requirements, the hybrid controller is guaranteed to enforce the desired specifications by construction thereby reducing the need for formal verification.     

Symbolic PathFinder: integrating symbolic execution with model checking for Java bytecode analysis

Symbolic PathFinder (SPF) is a software analysis tool that combines symbolic execution with model checking for automated test case generation and error detection in Java bytecode programs. In SPF, programs are executed on symbolic inputs representing multiple concrete inputs and the values of program variables are represented by expressions over those symbolic inputs. Constraints over these expressions are generated from the analysis of different paths through the program. The constraints are solved with off-the-shelf solvers to determine path feasibility and to generate test inputs. Model checking is used to explore different symbolic program executions, to systematically handle aliasing in the input data structures, and to analyze the multithreading present in the code. SPF incorporates techniques for handling input data structures, strings, and native calls to external libraries, as well as for solving complex mathematical constraints. We describe the tool and its application at NASA, in academia, and in industry.     

Incremental attribute evaluation through recursive procedures

Incremental semantic analysis in a programming environment based on Attribute Grammars is performed by an Incremental Attribute Evaluator (IAE). Current IAEs are either table-driven or make extensive use of graph structures to schedule reevaluation of attributes. A method of compiling an Ordered Attribute Grammar into mutually recursive procedures is proposed. These procedures form an optimal time Incremental Attribute Evaluator for the attribute grammar, which does not require any graphs or tables.     

Symbolic systems,explicit properties: on hybrid approaches for LTL symbolic model checking

In this work we study hybrid approaches to LTL symbolic model checking; that is, approaches that use explicit representations of the property automaton, whose state space is often quite manageable, and symbolic representations of the system, whose state space is typically exceedingly large. We compare the effects of using, respectively, (i) a purely symbolic representation of the property automaton, (ii) a symbolic representation, using logarithmic encoding, of explicitly compiled property automaton, and (iii) a partitioning of the symbolic state space according to an explicitly compiled property automaton. We apply this comparison to three model-checking algorithms: the doubly-nested fixpoint algorithm of Emerson and Lei, the reduction of emptiness to reachability of Biere et al., and the singly-nested fixpoint algorithm of Bloem et al. for weak automata. The emerging picture from our study is quite clear, hybrid approaches outperform pure symbolic model checking, while partitioning generally performs better than logarithmic encoding. The conclusion is that the hybrid approaches benefit from state-of-the-art techniques in semantic compilation of LTL properties. Partitioning gains further from the fact that the image computation is applied to smaller sets of states.     

Mathcad的符号计算在结构化学中的应用

为了高效、快捷地进行结构化学计算，此文选用了数学软件Mathcad2001 Professional作为工具，利用它的符号计算功能，针对结构化学中六类典型的复杂运算问题，进行了编程计算，取得了满意的结果。并对算例的运算原理和编程技术，作出了分析总结。这将有助于读者深入了解Mathcad的功能和掌握使用Mathcad进行结构化学计算的方法和技巧。研究表明，Mathcad符号计算功能强大，它的算式格式和数学语言相似，易于编程、理解和应用，非常适用于结构化学的研究和教学。     

Synthesis of parallel recursive programs in structural functional models

The problem of synthesis of parallel recursive programs from nonprocedural specifications is considered. To solve this problem, a special calculus is proposed. Constructing a scheme of a recursive procedure is discussed and a strategy and an algorithm of recursive and branching programs are proposed. The correctness of the algorithm is shown, and its efficiency is estimated.     

Symbolic evaluation of dimensionally regularized Feynman diagrams

A modification of the symbolic and algebraic manipulation program REDUCE is reported which allows the treatment of vector and gamma algebra in an arbitrary number of dimensions. The number of dimensions serves as a cut-off for divergences in the Feynman diagrams one has to evaluate in a theory like quantum gravity.     

Formal verification by symbolic evaluation of partially-ordered trajectories

Symbolic trajectory evaluation provides a means to formally verify properties of a sequential system by a modified form of symbolic simulation. The desired system properties are expressed in a notation combining Boolean expressions and the temporal logic next-time operator. In its simplest form, each property is expressed as an assertion [AC], where the antecedentA expresses some assumed conditions on the system state over a bounded time period, and the consequentC expresses conditions that should result. A generalization allows simple invariants to be established and proven automatically.The verifier operates on system models in which the state space is ordered by information content. By suitable restrictions to the specification notation, we guarantee that for every trajectory formula, there is a unique weakest state trajectory that satisfies it. Therefore, we can verify an assertion [AC] by simulating the system over the weakest trajectory forA and testing adherence toC. Also, establishing invariants correspond to simple fixed point calculations.This paper presents the general theory underlying symbolic trajectory evaluation. It also illustrates the application of the theory to the taks of verifying switch-level circuits as well as more abstract implementations.This research was supported by the Defense Advanced Research Projects Agency, ARPA Order Number 4976, by the National Science Foundation, under grant number MIP-8913667, by operating grant OGPO 109688 from the Natural Sciences and Engineering Research Council of Canada, and by a fellowship from the British Columbia Advanced Systems Institute.     

A unified symbolic evaluation framework for parallelizing compilers

The quality of many optimizations and analyses of parallelizing compilers depends significantly on the ability to evaluate symbolic expressions and on the amount of information available about program variables at arbitrary program points. In this paper, we describe an effective and unified symbolic evaluation framework that statically determines the values of variables and symbolic expressions, assumptions about and constraints between variable values, and the condition under which control flow reaches a program statement. We introduce the program context, a novel representation for comprehensive and compact control and data flow analysis information. Program contexts are described as first order logic formulas, which allows us to use public domain software for standard symbolic manipulation. Computations are represented as algebraic expressions defined over a program's problem size. Our symbolic evaluation techniques comprise accurate modeling of assignment and input/output statements, branches, loops, recurrences, arrays, and procedures. All of our techniques target both linear, as well as nonlinear, expressions and constraints. Efficiency of symbolic evaluation is highly improved by aggressive simplification techniques. A variety of examples, including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication, are used to illustrate the effectiveness of our approach. We present results from a preliminary implementation of our framework, which is used as part of a parallelizing compiler that demonstrates the potential performance gains achievable by employing symbolic evaluation to support program parallelization.     

An evaluation of the effectiveness of symbolic testing

The effectiveness in discovering errors of symbolic evaluation and of testing sad static program analysis are studied. The three techniques are applied to a diverse collection of programs and the results compared. Symbolic evaluation is used to carry out symbolic testing and to generate symbolic systems of path predicates. The use of the predicates for automated test data selection is analysed. Several conventional types of program testing strategies are evaluated. The strategies include branch testing, structured testing and testing on input values having special properties. The static source analysis techniques that are studied include anomaly analysis and interface analysis. Examples are included which describe typical situations in which one technique is reliable but another unreliable. The effectiveness of symbolic testing is compared with testing on actual data and with the use of an integrated methodology that includes both testing and static source analysis. Situations in which symbolic testing is difficult to apply or not effective are discussed. Different ways in which symbolic evaluation can be used for generating test data are described. Those ways for which it is most effective are isolated. The paper concludes with a discussion of the most effective uses to which symbolic evaluation can he put in an integrated system which contains all three of the validation techniques that are studied.     

Efficient evaluation for a subset of recursive queries

We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluation of the transformed program the bindings will be used to restrict the set of database facts consulted.     

Modeling and simulation of structural components in recursive closed-loop multibody systems

Passenger cars, transit buses, railroad vehicles, off-highway trucks, earth moving equipment and construction machinery contain structural and light-fabrications (SALF) components that are prone to excessive vibration due to rough terrains and work-cycle loads’ excitations. SALF components are typically modeled as flexible components in the multibody system allowing the analysts to predict elastic deformation and hence the stress levels under different loading conditions. Including SALF component in the multibody system typically generates closed-kinematic loops. This paper presents an approach for integrating SALF modeling capabilities as a flexible body in a general-purpose multibody dynamics solver that is based on joint-coordinates formulation with the ability to handle closed-kinematic loops. The spatial algebra notation is employed in deriving the spatial multibody dynamics equations of motion. The system kinematic topology matrix is used to project the Cartesian quantities into the joint subspace, leading to a condensed set of nonlinear equations with minimum number of generalized coordinates. The proposed flexible body formulation utilizes the component mode synthesis approach to reduce the large number of finite element degrees of freedom to a small set of generalized modal coordinates. The resulting reduced flexible body model has two main characteristics: the stiffness matrix is constant while the mass matrix depends on the elastic modal coordinates. A consistent set of pre-computed inertia shape integrals are identified and used to update the modal mass matrix at each time step. The implementation of the component mode synthesis approach in a closed-loop recursive multibody formulation is presented. The kinematic equations are modified to include the effect of the flexible body modal elastic coordinates. Also, modified constraint equations that include the effect of flexibility at the joint connections and the necessary details of the Jacobian matrix are presented. Baumgarte stabilization approach is used to stabilize the constraint equations without using iterative schemes. A sample results for flexible body impeded in a closed system will be presented to demonstrate the above mentioned approach.     

Symbolic computation with sequences

We present several classes of univariate sequences and sketch some algorithms for computing with sequences from these classes. The text was submitted by the author in English.     

Symbolic execution with abstraction

We address the problem of error detection for programs that take recursive data structures and arrays as input. Previously we proposed a combination of symbolic execution and model checking for the analysis of such programs: we put a bound on the size of the program inputs and/or the search depth of the model checker to limit the search state space. Here we look beyond bounded model checking and consider state matching techniques to limit the state space. We describe a method for examining whether a symbolic state that arises during symbolic execution is subsumed by another symbolic state. Since the number of symbolic states may be infinite, subsumption is not enough to ensure termination. Therefore, we also consider abstraction techniques for computing and storing abstract states during symbolic execution. Subsumption checking determines whether an abstract state is being revisited, in which case the model checker backtracks—this enables analysis of an under-approximation of the program behaviors. We illustrate the technique with abstractions for lists and arrays. We also discuss abstractions for more general data structures. The abstractions encode both the shape of the program heap and the constraints on numeric data. We have implemented the techniques in the Java PathFinder tool and we show their effectiveness on Java programs. This paper is an extended version of Anand et al. (Proceedings of SPIN, pp. 163–181, 2006).     

A generalization of the differential approach to recursive query evaluation

The differential (or seminaive) approach to query evaluation in function free, recursively defined, Horn clauses was recently proposed as an improvement to the naive bottom-up evaluation strategy. In this paper, we extend the approach to efficiently accomodate n recursively defined predicates in the body of a Horn clause.     

On the bottom—up evaluation of recursive queries

In this article, we present an optimal bottom-up evaluation method for handling both linear and nonlinear recursion. Based on the well-known magic-set method, we develop a technique: labeling to record the cyclic paths during the execution of the first phase of the magic-set method and suspending the computation for the cyclic data in the second phase to avoid the redundant evaluation. Then we postpone this computation to an iteration process (the third phase) which evaluates the remaining answers only along each cyclic path. In this way, we can guarantee the completeness. In addition, for a large class of programs we further optimize our method by elaborating the iteration process and generating most answers for each cyclic path directly from the intermediate results instead of evaluating them by performing algebraic operations (after some of the answers for the first cyclic path are produced). Because the cost of generating an answer is much less than that of evaluating an answer, this optimization is significant. © 1996 John Wiley & Sons, Inc.     

Query evaluation in recursive databases: bottom-up and top-down reconciled

It is desirable to answer queries posed to deductive databases by computing fixpoints because such computations are directly amenable to set-oriented fact processing. However, the classical fixpoint procedures based on bottom-up processing — the naive and semi-naive methods — are rather primitive and often inefficient. In this article, we rely on bottom-up meta-interpretation for formalizing a new fixpoint procedure that performs a different kind of reasoning: We specify a top-down query answering method, which we call the Backward Fixpoint Procedure. Then, we reconsider query evaluation methods for recursive databases. First, we show that the methods based on rewriting on the one hand, and the methods based on resolution on the other hand, implement the Backward Fixpoint Procedure. Second, we interpret the rewritings of the Alexander and Magic Set methods as specializations of the Backward Fixpoint Procedure. Finally, we argue that such a rewriting is also needed in a database context for implementing efficiently the resolution-based methods. Thus, the methods based on rewriting and the methods based on resolution implement the same top-down evaluation of the original database rules by means of auxiliary rules processed bottom-up.