Undivided and Indistinguishable Histories in Branching-Time Logics

In the tree-like representation of Time, two histories are undivided at a moment t whenever they share a common moment in the future of t. In the present paper, it will first be proved that Ockhamist and Peircean branching-time logics are unable to express some important sentences in which the notion of undividedness is involved. Then, a new semantics for branching-time logic will be presented. The new semantics is based on trees endowed with an indistinguishability function, a generalization of the notion of undividedness. It will be shown that Ockhamist and Peircean semantics can be viewed as limit cases of the semantics developed in this paper.     

Über die Konvergenz des Relaxationsverfahrens bei nicht-negativen und diagonaldominanten Matrizen

Zusammenfassung In der folgenden Arbeit werden zunächst die Begriffe Gesamtschrittverfahren, Einzelschrittverfahren und Relaxationsverfahren allgemein formuliert und dann auf allgemeine lineare Gleichungssysteme angewandt. Im Spezialfall einer Matrix mit verschwindender Hauptdiagonale erhält man so die bekanntenJacobi-, Gauss-Seidel- und Relaxationsverfahren. Satz 1 macht eine Aussage über die Konvergenz des Einzelschrittverfahrens bei allgemeinen, nicht-negativen Matrizen. Der Beweis verläuft ähnlich wie in einem bereits 1948 vonStein undRosenberg [2] behandelten Spezialfall. Als Korollar ergibt sich eine Aussage über die Konvergenz des Relaxationsverfahrens bei nicht-negativen Matrizen. Es wird ferner der Satz 2 über die Konvergenz des Relaxationsverfahrens bei diagonaldominanten Matrizen beweisen.

---

Summary In this paper we give a general definition what is meant by total-step-, single-step- and successive relaxation iterative method and we apply these concepts on systems of linear equations. In the special case of a matrix with zero diagonal entries we obtain the well knownJacobi-, Gauss-Seidel- and Relaxation iterative method. Theorem 1 gives conditions for the convergence of the singlestep-iterative method for general, non-negative matrices. The proof is similar to that given byStein andRosenberg in [2] (1948) for a special case. A corollary gives conditions for the convergence of the relaxation-iterative method for non-negative matrices. Further on we prove theorem 2 about the convergence of the relaxation-iterative method with diagonally dominant matrices.

     

Formalizing Synthetic Domain Theory

Synthetic Domain Theory (SDT) is a constructive variant of Domain Theory where all functions are continuous following Dana Scotts idea of domains as sets. Recently there have been suggested more abstract axiomatizations encompassing alternative notions of domain theory as, for example, stable domain theory.In this article a logical and axiomatic version of SDT capturing the essence of Domain Theory à la Scott is presented. It is based on a sufficiently expressive version of constructive type theory and fully implemented in the proof checker Lego. On top of this core SDT denotational semantics and program verification can be – and in fact has been – developed in a purely formal machine-checked way.The version of SDT we have chosen for this purpose is based on work by Reus and Streicher and can be regarded as an axiomatization of complete extensional PERs. This approach is a modification of Phoas complete -spaces and uses axioms introduced by Taylor.     

Eine bedingte Form der Integral-Ungleichung von Gronwall,leichte Verallgemeinerung eines Stabilitätssatzes von Perron und überlauffreie Skalierung von Analogrechenschaltungen

Zusammenfassung Es geht in dieser Arbeit in der Hauptsache darum, ein vorgelegtes Differentialgleichungssystem so zu skalieren, daß in der zugehörigen Analogrechnerschaltung die Spannungen an den Ausgängen der Integratoren die durch die Referenzspannung einerseits und durch das Auflösevermögen andererseits gesetzten Schranken nicht über- bzw. unterschreiten. Es werden Abschätzungssätze hergeleitet, die diese Frage im Apriori-Sinn, also ohne die Lösung des Differentialgleichungssystems zu kennen, zu lösen gestatten. Zur Abschätzung werden zunächst Normen, dannKamke-Normen verwendet. Der im Titel erwähnte Satz vonPerron ergibt sich durch spezielle Normengebung und Verzicht auf Abschätzung nach unten. Erschwert werden die Betrachtungen durch die relative Schwäche der Forderung, daß die rechte Seite des Systemsdx/dt=f(x,t) der Bedingung aus xa folgt f(x,t)v(t)x genüge (...:=Norm,a positiv reell). Dadurch scheint es bei Abschätzungen mitKamke-Normen nicht mehr möglich, von den in der Literatur über Existenzbeweise und Abschätzungssätze üblichen Methoden Gebrauch zu machen. Zur Lösung dieser Frage wird eine bedingte Form des bekannten Satzes vonGronwall (auch Satz vonBellman genannt) entwickelt.

---

A conditional version of the integral inequality of gronwall, a slight generalization of a stability theorem of perron, and overflow-free scaling of analogue computer set-ups

Summary The main subject of this paper is the scaling of a given set of differential equations in such a way that the output voltages of the integrators of the associated analogue computer set-up do not exceed certain upper and lower bounds imposed by the reference voltage and the limited power of resolution of the elements of the analogue computer. The paper gives a priori bounds on the solution of the differential set. Some of these bounds work with norms, others withKamke-norms.Perron's stability theorem mentioned in the title of this paper results by inserting special norms and neglecting lower bounds. A difficulty arises by the relative weakness of the condition xa implies f(x,t)v(t)x on the right hand side of the setdx/dt=f(x,t), where ... is any norm anda is a positive real constant. As a consequence of this, it seems no longer possible to use the usual techniques known from the literature on existence theorems and bounds for the solution of differential equations. To cope with this situation, a conditional version of the well-known theorem ofGronwall (also known by the name of Lemma ofBellman) will be derived.

---

Diese Arbeit ist Teil einer am Institut für Angewandte Mathematik der Technischen Hochschule München unter Anleitung von Herrn o. Prof. Dr. rer. nat. habil.J. Heinhold angefertigten Dissertation.     

OCL 1.4/5 vs. 2.0 Expressions Formal semantics and expressiveness

A type inference system and a big-step operational semantics for expressions of the Object Constraint Language (OCL), the declarative and navigational constraint language for the Unified Modeling Language (UML), are provided; the account is mainly based on OCL 1.4/5, but also includes the main features of OCL 2.0. The formal systems are parameterised in terms of UML static structures and UML object models, which are treated abstractly. It is proved that the operational semantics satisfies a subject reduction property with respect to the type inference system. Proceeding from the operational semantics and providing a denotational semantics, pure OCL 2.0 expressions are shown to exactly represent the primitive recursive functions, whereas pure OCL 1.4/5 expressions are Turing complete.     

Modelling structures in generic space, a condition for adaptiveness of monitoring cognitive agent

The adaptiveness of agents is one of the basic conditions for the autonomy. This paper describes an approach of adaptiveness forMonitoring Cognitive Agents based on the notion of generic spaces. This notion allows the definition of virtual generic processes so that any particular actual process is then a simple configuration of the generic process, that is to say a set of values of parameters. Consequently, generic domain ontology containing the generic knowledge for solving problems concerning the generic process can be developed. This lead to the design of Generic Monitoring Cognitive Agent, a class of agent in which the whole knowledge corpus is generic. In other words, modeling a process within a generic space becomes configuring a generic process and adaptiveness becomes genericity, that is to say independence regarding technology. In this paper, we present an application of this approach on Sachem, a Generic Monitoring Cognitive Agent designed in order to help the operators in operating a blast furnace. Specifically, the NeuroGaz module of Sachem will be used to present the notion of a generic blast furnace. The adaptiveness of Sachem can then be noted through the low cost of the deployment of a Sachem instance on different blast furnaces and the ability of NeuroGaz in solving problem and learning from various top gas instrumentation.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Unitary immersions of nonlinear systems

In this paper, we define what we call a unitary immersion of a nonlinear system. We observe that, for classical Hamiltonian systems, this notion contains, in some sense, the concept of quantization. We restrict our attention to degree-zero unitary immersions, where all observation functions must be represented by operators of the type multiplication by a function. We show that the problem of classifying such degree-zero unitary immersions of a given nonlinear system is not obvious. In some cases, we solve this problem.Chargé de Recherche au CNRS.Maître de Conférences.     

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.     

Global storage cells for attributes in an attribute grammar

Summary Very much space is needed to store the values of all attribute instances in an attributed tree at the corresponding nodes; for that reason global cells are often used to store values of attribute instances. But these global cells must contain the right value at the right time, and, therefore, not all evaluation sequences of attribute instances are admissible, if one uses global cells.In this paper we will study first the problem arising during the construction of such admissible evaluation sequences for attributed trees, if no special property of an underlying ag is presumed. This will lead to a number of restrictions on the practically allowed use of global cells. After that we will provide a method for the construction of admissible evaluation sequences for arbitrary attribute trees of given attribute grammars, if global cells are used in the restricted sense. The proposed method is independent of special classes of attribute grammars and can be used with arbitrary evaluator generators.     

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.     

Reaping the whirlwind: Reply to Harnad's “other bodies,other minds”

Harnad's proposed robotic upgrade of Turing's Test (TT), from a test of linguistic capacity alone to a Total Turing Test (TTT) of linguisticand sensorimotor capacity, conflicts with his claim that no behavioral test provides even probable warrant for attributions of thought because there is no evidence of consciousness besides private experience. Intuitive, scientific, and philosophical considerations Harnad offers in favor of his proposed upgrade are unconvincing. I agree with Harnad that distinguishing real from as if thought on the basis of (presence or lack of) consciousness (thus rejecting Turing (behavioral) testing as sufficient warrant for mental attribution)has the skeptical consequence Harnad accepts — there is in factno evidence for me that anyone else but me has a mind. I disagree with hisacceptance of it! It would be better to give up the neo-Cartesian faith in private conscious experience underlying Harnad's allegiance to Searle's controversial Chinese Room Experiment than give up all claim to know others think. It would be better to allow that (passing) Turing's Test evidences — evenstrongly evidences — thought.     

Effects of computers on Japanese schools

In this paper I consider how the computer can or should be accepted in Japanese schools. The concept of teaching in Japan stresses learning from a long-term perspective. Whereas in the instructional technology, on which the CAI or the Tutoring System depends, step-by-step attainments in relatively short time are emphasized. The former is reluctant in using the computer, but both share the Platonic perspective which are goal-oriented. However, The Socratic teacher, who intends to activate students' innate disposition to be better, would find another way of teaching and use of the computer.     

States and the free orthogonality monoid

Let (X, #) be an orthogonality space such that the lattice C(X, #) of closed subsets of (X, #) is orthomodular and let (, ) denote the free orthogonality monoid over (X, #). Let C₀(, ) be the subset of C(, ), consisting of all closures of bounded orthogonal sets. We show that C₀(, ) is a suborthomodular lattice of C(, ) and we provide a necessary and sufficient condition for C₀(, ) to carry a full set of dispersion free states.The work of the second author on this paper was supported by National Science Foundation Grant GP-9005.     

A New Implementation of Automath

This paper presents aut, a modern Automath checker. It is a straightforward re-implementation of the Zandleven Automath checker from the seventies. It was implemented about five years ago, in the programming language C. It accepts both the AUT-68 and AUT-QE dialects of Automath. This program was written to restore a damaged version of Jutting's translation of Landau's Grundlagen. Some notable features: It is fast. On a 1 GHz machine it will check the full Jutting formalization (736 K of nonwhitespace Automath source) in 0.6 seconds. Its implementation of -terms does not use named variables or de Bruijn indices (the two common approaches) but instead uses a graph representation. In this representation variables are represented by pointers to a binder. The program can compile an Automath text into one big Automath single line-style -term. It outputs such a term using de Bruijn indices. (These -terms cannot be checked by modern systems like Coq or Agda, because the -typed -calculi of de Bruijn are different from the -typed -calculi of modern type theory.)The source of aut is freely available on the Web at the address .     

A theory of nonmonotonic rule systems I

We introduce here the study of generalnonmonotonic rule systems. These deal with situations where a conclusion is drawn from a system of beliefsS (and seen to be inS), basedboth on some premises being inS and on some restraints not being inS. In the monotone systems of traditional logic there are no restraints, conclusions are drawn solely based on premises being inS. Nonmonotonic rule systems capture the essential syntactic, semantic, and algorithmic features of many nonmonotone systems such as default logic, negation as failure, truth maintenance, autoepistemic logic, and also important combinatorial questions from mathematics such as the marriage problem. This reveals semantics and syntax and proof procedures and algorithms for computing belief sets in many cases where none were previously available and entirely uniformly. In particular, we introduce and study deductively closed sets, extensions and weak extensions. Semantics of nonmonotonic rule systems is studied in part II of this paper and extensions to predicate classical, intuitionistic, and modal logics are left to a later paper.Work partially supported by NSF grant RII-8610671 and Kentucky EPSCoR program and ARO contract DAAL03-89-K-0124.Work partially supported by NSF grant DMS-8902797 and ARO contract DAAG629-85-C-0018.Work partially supported by NSF grant DMS-8702473.     

Dualities between alternative semantics for logic programming and nonmonotonic reasoning

The Gelfond-Lifschitz operator associated with a logic program (and likewise the operator associated with default theories by Reiter) exhibits oscillating behavior. In the case of logic programs, there is always at least one finite, nonempty collection of Herbrand interpretations around which the Gelfond-Lifschitz operator bounces around. The same phenomenon occurs with default logic when Reiter's operator is considered. Based on this, a stable class semantics and extension class semantics has been proposed. The main advantage of this semantics was that it was defined for all logic programs (and default theories), and that this definition was modelled using the standard operators existing in the literature such as Reiter's operator. In this paper our primary aim is to prove that there is a very interestingduality between stable class theory and the well-founded semantics for logic programming. In the stable class semantics, classes that were minimal with respect to Smyth's power-domain ordering were selected. We show that the well-founded semantics precisely corresponds to a class that is minimal w.r.t. Hoare's power domain ordering: the well-known dual of Smyth's ordering. Besides this elegant duality, this immediately suggests how to define a well-founded semantics for default logic in such a way that the dualities that hold for logic programming continue to hold for default theories. We show how the same technique may be applied to strong autoepistemic logic: the logic of strong expansions proposed by Marek and Truszczynski.     

Networked Collaborative Learning in the Study of Modern History and Literature

Many teachers adopt networked collaborative learning strategies even though these approaches systematically increase the time needed to deal with a given subject. But who's making them do it?. Probably there has to be a return on investment, in terms of time and obviously in terms of educational results, which justifies that commitment. After surveying the particular features of two experimental projects based on networked collaborative learning, the paper will then offer a series of thoughts triggered by observation of the results and the dynamics generated by this specific approach. The purpose of these thoughts is to identify some key factors that make it possible to measure the real added value produced by network collaboration in terms of the acquisition of skills, knowledge, methods and attitudes that go beyond the mere learning of contents (however fundamental this may be). And it is precisely on the basis of these considerations that teachers usually answer the above question, explaining who (or what) made them do it!.     

Extremal Relations between Additive Loss Functions and the Kolmogorov Complexity

Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) K(₁... _N ) is attained, given the cost f( _i ) of a message ₁... _N . Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function f( _i ) – K(₁... _N ) is studied. Here, is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function.