Sound and Complete Qualitative Simulation Needs “Quantitative” Filtering

The AI methodology of qualitative reasoning furnishes useful tools to scientists and engineers who need to deal with incomplete system knowledge during design, analysis, or diagnosis tasks. Qualitative simulators have a theoretical soundness guarantee; they cannot overlook any concrete equation implied by their input. On the other hand, the basic qualitative simulation algorithms have been shown to suffer from the incompleteness problem; they may allow non-solutions of the input equation to appear in their output. The question of whether a simulator with purely qualitative input which never predicts spurious behaviors can ever be achieved by adding new filters to the existing algorithm has remained unanswered. In this paper, we show that, if such a sound and complete simulator exists, it will have to be able to handle numerical distinctions with such a high precision that it must contain a component that would better be called a quantitative, rather than qualitative reasoner. This is due to the ability of the pure qualitative format to allow the exact representation of the members of a rich set of numbers.     

The dynamic clusters method in nonhierarchical clustering

Given a finite setE R ⁿ, the problem is to find clusters (or subsets of similar points inE) and at the same time to find the most typical elements of this set. An original mathematical formulation is given to the problem. The proposed algorithm operates on groups of points, called samplings (samplings may be called multiple centers or cores); these samplings adapt and evolve into interesting clusters. Compared with other clustering algorithms, this algorithm requires less machine time and storage. We provide some propositions about nonprobabilistic convergence and a sufficient condition which ensures the decrease of the criterion. Some computational experiments are presented.     

Sometime = always + recursion ≡ always on the equivalence of the intermittent and invariant assertions methods for proving inevitability properties of programs

Summary We propose and compare two induction principles called always and sometime for proving inevitability properties of programs. They are respective formalizations and generalizations of Floyd invariant assertions and Burstall intermittent assertions methods for proving total correctness of sequential programs whose methodological advantages or disadvantages have been discussed in a number of previous papers. Both principles are formalized in the abstract setting of arbitrary nondeterministic transition systems and illustrated by appropriate examples. The sometime method is interpreted as a recursive application of the always method. Hence always can be considered as a special case of sometime. These proof methods are strongly equivalent in the sense that a proof by one induction principle can be rewritten into a proof by the other one. The first two theorems of the paper show that an invariant for the always method can be translated into an invariant for the sometime method even if every recursive application of the later is required to be of finite length. The third and main theorem of the paper shows how to translate an invariant for the sometime method into an invariant for the always method. It is emphasized that this translation technique follows the idea of transforming recursive programs into iterative ones. Of course, a general translation technique does not imply that the original sometime invariant and the resulting always invariant are equally understandable. This is illustrated by an example.     

A Philosophical Approach to the Concept of Data Model: Is a Data Model, in Fact, a Model?

The design of the database is crucial to the process of designing almost any Information System (IS) and involves two clearly identifiable key concepts: schema and data model, the latter allowing us to define the former. Nevertheless, the term model is commonly applied indistinctly to both, the confusion arising from the fact that in Software Engineering (SE), unlike in formal or empirical sciences, the notion of model has a double meaning of which we are not always aware. If we take our idea of model directly from empirical sciences, then the schema of a database would actually be a model, whereas the data model would be a set of tools allowing us to define such a schema.The present paper discusses the meaning of model in the area of Software Engineering from a philosophical point of view, an important topic for the confusion arising directly affects other debates where model is a key concept. We would also suggest that the need for a philosophical discussion on the concept of data model is a further argument in favour of institutionalizing a new area of knowledge, which could be called: Philosophy of Engineering.     

Property preserving abstractions for the verification of concurrent systems

We study property preserving transformations for reactive systems. The main idea is the use of simulations parameterized by Galois connections (, ), relating the lattices of properties of two systems. We propose and study a notion of preservation of properties expressed by formulas of a logic, by a function mapping sets of states of a systemS into sets of states of a systemS'. We give results on the preservation of properties expressed in sublanguages of the branching time -calculus when two systemsS andS' are related via (, )-simulations. They can be used to verify a property for a system by verifying the same property on a simpler system which is an abstraction of it. We show also under which conditions abstraction of concurrent systems can be computed from the abstraction of their components. This allows a compositional application of the proposed verification method.This is a revised version of the papers [2] and [16]; the results are fully developed in [28].This work was partially supported by ESPRIT Basic Research Action REACT.Verimag is a joint laboratory of CNRS, Institut National Polytechnique de Grenoble, Université J. Fourier and Verilog SA associated with IMAG.     

One Connection between Standard Invariance Conditions on Modal Formulas and Generalized Quantifiers

The language of standard propositional modal logic has one operator ( or ), that can be thought of as being determined by the quantifiers or , respectively: for example, a formula of the form is true at a point s just in case all the immediate successors of s verify .This paper uses a propositional modal language with one operator determined by a generalized quantifier to discuss a simple connection between standard invariance conditions on modal formulas and generalized quantifiers: the combined generalized quantifier conditions of conservativity and extension correspond to the modal condition of invariance under generated submodels, and the modal condition of invariance under bisimulations corresponds to the generalized quantifier being a Boolean combination of and .     

Evaluation of Queries under Closed-World Assumption

The minimal entailment Min has been characterized elsewhere by where Cn is the first-order consequence operation, P is a set of clauses (indefinite deductive data base; in short: a data base), is a clause (a query), and Pos is the set of positive (that is, bodiless) ground clauses. In this paper, we address the problem of the computational feasibility of criterion (1). Our objective is to find a query evaluation algorithm that decides P Min by what we call indefinite modeling, without actually computing all ground positive consequences of P and P {}. For this purpose, we introduce the concept of minimal indefinite Herbrand model MP of P, which is defined as the set of subsumption-minimal ground positive clauses provable from P. The algorithm first computes MP by finding the least fixed-point of an indefinite consequence operator TIP. Next, the algorithm verifies whether every ground positive clause derivable from MP {} by one application of the parallel positive resolution rule (in short: the PPR rule) is subsumed by an element of MP. We prove that the PPR rule, which can derive only positive clauses, is positively complete, that is, every positive clause provable from a data base P is derivable from P by means of subsumption and finitely many applications of PPR. From this we conclude that the presented algorithm is partially correct and that it eventually halts if both P and MP are finite. Moreover, we indicate how the algorithm can be modified to handle data bases with infinite indefinite Herbrand models. This modification leads to a concept of universal model that allows for nonground clauses in its Herbrand base and appears to be a good candidate for representation of indefinite deductive data bases.     

Fuzzy measurement in the Mishnah and the Talmud

I discuss the attitude of Jewish law sources from the 2nd–:5th centuries to the imprecision of measurement. I review a problem that the Talmud refers to, somewhat obscurely, as impossible reduction. This problem arises when a legal rule specifies an object by referring to a maximized (or minimized) measurement function, e.g., when a rule applies to the largest part of a divided whole, or to the first incidence that occurs, etc. A problem that is often mentioned is whether there might be hypothetical situations involving more than one maximal (or minimal) value of the relevant measurement and, given such situations, what is the pertinent legal rule. Presumption of simultaneous occurrences or equally measured values are also a source of embarrassment to modern legal systems, in situations exemplified in the paper, where law determines a preference based on measured values. I contend that the Talmudic sources discussing the problem of impossible reduction were guided by primitive insights compatible with fuzzy logic presentation of the inevitable uncertainty involved in measurement. I maintain that fuzzy models of data are compatible with a positivistic epistemology, which refuses to assume any precision in the extra-conscious world that may not be captured by observation and measurement. I therefore propose this view as the preferred interpretation of the Talmudic notion of impossible reduction. Attributing a fuzzy world view to the Talmudic authorities is meant not only to increase our understanding of the Talmud but, in so doing, also to demonstrate that fuzzy notions are entrenched in our practical reasoning. If Talmudic sages did indeed conceive the results of measurements in terms of fuzzy numbers, then equality between the results of measurements had to be more complicated than crisp equations. The problem of impossible reduction could lie in fuzzy sets with an empty core or whose membership functions were only partly congruent. Reduction is impossible may thus be reconstructed as there is no core to the intersection of two measures. I describe Dirichlet maps for fuzzy measurements of distance as a rough partition of the universe, where for any region A there may be a non-empty set of - _A (upper approximation minus lower approximation), where the problem of impossible reduction applies. This model may easily be combined with probabilistic extention. The possibility of adopting practical decision standards based on -cuts (and therefore applying interval analysis to fuzzy equations) is discussed in this context. I propose to characterize the uncertainty that was presumably capped by the old sages as U-uncertainty, defined, for a non-empty fuzzy set A on the set of real numbers, whose -cuts are intervals of real numbers, as U(A) = 1/h(A) ₀ ^h(A) log [1+(A)]d, where h(A) is the largest membership value obtained by any element of A and (A) is the measure of the -cut of A defined by the Lebesge integral of its characteristic function.     

Software engineering programmes are not computer science programmes

Programmes in Software Engineering have become a source of contention in many universities. Some Computer Science departments, many of which have used that phrase to describe individual courses for decades, claim software engineering as part of their discipline. However, Engineering faculties claim Software Engineering as a new speciality in the family of engineering disciplines. This paper discusses the differences between traditional computer science programmes and most engineering programmes and argues that we need programmes that follow the traditional engineering approach to professional education and educate engineers whose speciality within engineering is software construction. One such programme is described.     

Crankback Prediction in Hierarchical ATM Networks

When an ATM node discovers that it cannot continue the setup of a virtual channel under the requested Quality of Service (QoS), it initiates a backtracking procedure called crankback. We propose a novel scheme, referred to as crankback prediction, that decreases the crankback overhead. Under the proposed scheme, nodes check during the connection admission control procedure whether the establishment of a virtual channel has a good chance to be admitted over the entire designated route. If this is not the case, crankback is initiated even before a particular QoS parameter is violated. The main idea behind the proposed scheme is to allocate a quota to the Peer Groups (PGs) along the message path, and then to suballocate this quota to the child PGs of these PGs. This process continues recursively until reaching the 1-level PG, which contains only physical nodes. The main advantage of the proposed scheme is that it lowers the setup delay and the processing and communication load imposed by signaling messages that establish unused portions of Virtual Channels (VCs)     

Design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems

This paper describes a unified variational theory for design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems for shape, nonshape, material and mechanical properties selection, as well as control problems. The concept of an adjoint system, the principle of virtual work and a Lagrangian-Eulerian formulation to describe the deformations and the design variations are used to develop a unified view point. A general formula for design sensitivity analysis is derived and interpreted for usual performance functionals. Analytical examples are utilized to demonstrate the use of the theory and give insights for application to more complex problems that must be treated numerically.Derivatives The comma notation for partial derivatives is used, i.e. G,_u = G/u. An upper dot represents material time derivative, i.e. ü = ²u/t². A prime implies derivative with respect to the time measured in the reference time-domain, i.e. u = du/d.     

Deep X-ray lithography using mask with integrated electrothermal actuator

We present a deep X-ray mask with integrated bent-beam electrothermal actuator for the fabrication of 3D microstructures with curved surface. The mask absorber is electroplated on the shuttle mass, which is supported by a pair of 20-m-thick single crystal silicon bent-beam electrothermal actuators and oscillated in a rectilinear direction due to the thermal expansion of the bent-beams. The width of each bent-beam is 10 m or 20 m and the length and bending angle are 1 mm and 0.1 rad, respectively, and the shuttle mass size is 1 mm × 1 mm. For 10-m-wide bent-beams, the shuttle mass displacement is around 15 m at 180 mW (3.6 V) dc input power. For 20-m-wide bent-beams, the shuttle mass displacement is around 19 m at 336 mW (4.2 V) dc input power. Sinusoidal cross-sectional PMMA microstructures with a pitch of 40 m and a height of 20 m are fabricated by 0.5 Hz, 20-m-amplitude sinusoidal shuttle mass oscillation.This research, under the contract project code MS-02-338-01, has been supported by the Intelligent Microsystem Center, which carries out one of the 21st centurys Frontier R & D Projects sponsored by the Korea Ministry of Science & Technology. Experiments at PLS were supported in part by MOST and POSCO.     

Unextendible Product Bases and Locally Unconvertible Bound Entangled States

Mutual convertibility of bound entangled states under local quantum operations and classical communication (LOCC) is studied. We focus on states associated with unextendible product bases (UPB) in a system of three qubits. A complete classification of such UPBs is suggested. We prove that for any pair of UPBs S and T the associated bound entangled states _S and _T cannot be converted to each other by LOCC, unless S and T coincide up to local unitaries. More specifically, there exists a finite precision (S,T) > 0 such that for any LOCC protocol mapping _S into a probabilistic ensemble (p, ), the fidelity between _T and any possible final state satisfies F(_T, ) = 1 - (S,T).PACS: 03.65.Bz; 03.67.-a; 89.70+c.     

Almost surely continuous solutions of a nonlinear stochastic integral equation

A nonlinear stochastic integral equation of the Hammerstein type in the formx(t; ) = h(t, x(t; )) + _s k(t, s; )f(s, x(s; ); )d(s) is studied wheret S, a measure space with certain properties, , the supporting set of a probability measure space (,A, P), and the integral is a Bochner integral. A random solution of the equation is defined to be an almost surely continuousm-dimensional vector-valued stochastic process onS which is bounded with probability one for eacht S and which satisfies the equation almost surely. Several theorems are proved which give conditions such that a unique random solution exists. AMS (MOS) subject classifications (1970): Primary; 60H20, 45G99. Secondary: 60G99.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

On characterizing the “knee” of the Pareto curve based on Normal-Boundary Intersection

This paper deals with the issue of generating one Pareto optimal point that is guaranteed to be in a desirable part of the Pareto set in a given multicriteria optimization problem. A parameterization of the Pareto set based on the recently developed normal-boundary intersection technique is used to formulate a subproblem, the solution of which yields the point of maximum bulge, often referred to as the knee of the Pareto curve. This enables the identification of the good region of the Pareto set by solving one nonlinear programming problem, thereby bypassing the need to generate many Pareto points. Further, this representation extends the concept of the knee for problems with more than two objectives. It is further proved that this knee is invariant with respect to the scales of the multiple objective functions.The generation of this knee however requires the value of each objective function at the minimizer of every objective function (the pay-off matrix). The paper characterizes situations when approximations to the function values comprising the pay-off matrix would suffice in generating a good approximation to the knee. Numerical results are provided to illustrate this point. Further, a weighted sum minimization problem is developed based on the information in the pay-off matrix, by solving which the knee can be obtained.     

Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.     

Proof Reflection in Coq

We formalize natural deduction for first-order logic in the proof assistant Coq, using de Bruijn indices for variable binding. The main judgment we model is of the form d[:], stating that d is a proof term of formula under hypotheses it can be viewed as a typing relation by the Curry–Howard isomorphism. This relation is proved sound with respect to Coq's native logic and is amenable to the manipulation of formulas and of derivations. As an illustration, we define a reduction relation on proof terms with permutative conversions and prove the property of subject reduction.     

Finite canonical rewriting systems for congruences generated by concurrency relations

WhenC is a concurrency relation on alphabet , then ^*/= _C is a free partially commutative monoid. Here we show that it is decidable in polynomial time whether or not there exists a finite canonical rewriting systemR on such that the congruences _R ^* generated byR and = _C induced byC coincide. Further, in case such a systemR exists, one such system can be determined in polynomial time.     

Mobile Agent-Based Management in the INSERT Project

This paper describes work carried out atUniversity College London to evaluate the use of MobileAgents (MA), written in Java, in network and systemmanagement. The work draws on experience fromconventional management systems based on ISO CommonManagement Information Protocol (CMIP) andInternet Simple Network ManagementProtocol (SNMP). These systems make use of theconcept of a Managed Object (MO). The paper describes the way in which the MOconcept has been translated into a form suitable forMA-based management and how the features of the Javalanguage may be used to express management information and to implement MOs. A platform has beenimplemented which allows MOs to be instantiated,controlled and stored. The platform also allows the easyproduction of MAs, their launching into the system and their subsequent management. Details of theplatform implementation are given and an initialassessment of performance is presented.