Adding a temporal dimension to a logic system

We introduce a methodology whereby an arbitrary logic system L can be enriched with temporal features to create a new system T(L). The new system is constructed by combining L with a pure propositional temporal logic T (such as linear temporal logic with Since and Until) in a special way. We refer to this method as adding a temporal dimension to L or just temporalising L. We show that the logic system T(L) preserves several properties of the original temporal logic like soundness, completeness, decidability, conservativeness and separation over linear flows of time. We then focus on the temporalisation of first-order logic, and a comparison is make with other first-order approaches to the handling of time.     

Comparing text editions with the aid of the computer

The aim of this paper is to reveal the limitations of relying on fingerprint formulas or signature positions to identify printed editions, in the manner of the STCN project. The paper proposes that scanned images of texts be used to identify editions.Ben J. P. Salemans is a philologist with special interest in the use of the computer as a scientific tool in literary, philological and cultural-historical research. His Ph.D. project is a study of automated text-genealogical research. He works as a computer consultant at the UCI computer centre of the University of Nijmegen.Dedicated to the memory of Marcel te Wilt ( 1993).     

Decision procedures for elementary sublanguages of set theory: XIII. Model graphs,reflection and decidability

Positive solutions to the decision problem for a class of quantified formulae of the first order set theoretic language based on , , =, involving particular occurrences of restricted universal quantifiers and for the unquantified formulae of , , =, {...}, , where {...} is the tuple operator and is a general choice operator, are obtained. To that end a method is developed which also provides strong reflection principles over the hereditarily finite sets. As far as finite satisfiability is concerned such results apply also to the unquantified extention of , , =, {...}, , obtained by adding the operators of binary union, intersection and difference and the relation of inclusion, provided no nested term involving is allowed.     

Nonblockability of Switches with the Cayley Graph Structure for Serial Transfer of Data Blocks. Generalized Hypercubes and Multidimensional Grids

A general method of conflictless arbitrary permutation of large data elements that can be divided into a multitude of smaller data blocks was considered for switches structured as the Cayley graphs. The method was specified for arbitrary permutations in the generalized hypercubes and multidimensional grids, and their characteristics were considered.     

Generating Boolean \mu-expressions

In this paper, we consider the class of Boolean -functions, which are the Boolean functions definable by -expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formulaE into an equivalent -expression-if possible-in time linear in E times , where E is the size ofE andn _m is the number of variables that occur more than once inE. As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing -functions fromk-formulas [17]. Furthermore, we show that recognizing Boolean -functions is co-NP-complete for functions essentially dependent on all variables and we give a bound close to co-NP for the general case.     

Total complexity and the inference of best programs

The problem of choosing a best program for a function presented by example is considered. General axioms for total complexity involving time and size measures are presented. For measures obeying the axioms, certain positive and negative results are obtained on the existence of effective algorithms for learning the best program.     

On-line Learning and the Metrical Task System Problem

The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship between these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include: An analysis of how two recent algorithms for the MTS problem can be applied to the problem of tracking the best expert in the decision-theoretic setting, providing good bounds and an approach of a much different flavor from the well-known multiplicative-update algorithms. An analysis showing how the standard randomized Weighted Majority (or Hedge) algorithm can be used for the problem of combining on-line algorithms on-line, giving much stronger guarantees than the results of Azar, Y., Broder, A., & Manasse, M. (1993). Proc ACM-SIAM Symposium on Discrete Algorithms (pp. 432–440) when the algorithms being combined occupy a state space of bounded diameter. A generalization of the above, showing how (a simplified version of) Herbster and Warmuth's weight-sharing algorithm can be applied to give a finely competitive bound for the uniform-space Metrical Task System problem. We also give a new, simpler algorithm for tracking experts, which unfortunately does not carry over to the MTS problem.Finally, we present an experimental comparison of how these algorithms perform on a process migration problem, a problem that combines aspects of both the experts-tracking and MTS formalisms.     

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.     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

Branch-and-bound and backtrack search on mesh-connected arrays of processors

In this paper we investigate the parallel complexity of backtrack and branch-and-bound search on the mesh-connected array. We present an (dN/logdN) lower bound for the time needed by arandomized algorithm to perform backtrack and branch-and-bound search of a tree of depthd on the N × N mesh, even when the depth of the tree is known in advance. The lower bound also holds for algorithms that are allowed to move tree-nodes and create multiple copies of the same tree-node.For the upper bounds we givedeterministic algorithms that are within a factor of 0(log^3/2 N) from our lower bound. Our algorithms do not make any assumption on the shape of the tree to be searched, do not know the depth of the tree in advance, and do not move tree-nodes nor create multiple copies of the same node.The best previously known algorithm for backtrack search on the mesh was randomized and required (dN/ logN) time. Our algorithm for branch-and-bound is the first algorithm that performs branch-and-bound search on a sparse network. Both the lower and the upper bounds extend to meshes of higher dimensions.Part of this work was done while the authors were at Harvard University.     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control

We consider the on-line competitiveness for scheduling a single resource non-preemptively in order to maximize its utilization. Our work examines this model when parameterizing an instance by a new value which we term the patience. This parameter measures each job's willingness to endure a delay before starting, relative to this same job's processing time. Specifically, the slack of a job is defined as the gap between its release time and the last possible time at which it may be started while still meeting its deadline. We say that a problem instance has patience , if each job with length J has a slack of at least ·J.Without any restrictions placed on the job characteristics, previous lower bounds show that no algorithm, deterministic or randomized, can guarantee a constant bound on the competitiveness of a resulting schedule. Previous researchers have analyzed a problem instance by parameterizing based on the ratio between the longest job's processing time and the shortest job's processing time. Our main contribution is to provide a fine-grained analysis of the problem when simultaneously parameterized by patience and the range of job lengths. We are able to give tight or almost tight bounds on the deterministic competitiveness for all parameter combinations.If viewing the analysis of each parameter individually, our evidence suggests that parameterizing solely on patience provides a richer analysis than parameterizing solely on the ratio of the job lengths. For example, in the special case where all jobs have the same length, we generalize a previous bound of 2 for the deterministic competitiveness with arbitrary slacks, showing that the competitiveness for any 0 is exactly 1+1/(+1). Without any bound on the job lengths, a simple greedy algorithm is (2+(1/))-competitive for any <0. More generally we will find that for any fixed ratio of job lengths, the competitiveness of the problem tends towards 1 as the patience is increased. The converse is not true, as for any fixed <0 we find that the competitiveness is bounded away from 1, no matter what further restrictions are placed on the ratio of job lengths.     

Change Detection in Overhead Imagery Using Neural Networks

Identifying interesting changes from a sequence of overhead imagery—as opposed to clutter, lighting/seasonal changes, etc.—has been a problem for some time. Recent advances in data mining have greatly increased the size of datasets that can be attacked with pattern discovery methods. This paper presents a technique for using predictive modeling to identify unusual changes in images. Neural networks are trained to predict before and after pixel values for a sequence of images. These networks are then used to predict expected values for the same images used in training. Substantial differences between the expected and actual values represent an unusual change. Results are presented on both multispectral and panchromatic imagery.     

On the Axioms of Scale Space Theory

We consider alternative scale space representations beyond the well-established Gaussian case that satisfy all reasonable axioms. One of these turns out to be subject to a first order pseudo partial differential equation equivalent to the Laplace equation on the upper half plane {(x, s) ^d × | s > 0}. We investigate this so-called Poisson scale space and show that it is indeed a viable alternative to Gaussian scale space. Poisson and Gaussian scale space are related via a one-parameter class of operationally well-defined intermediate representations generated by a fractional power of (minus) the spatial Laplace operator.     

The impact of artificial intelligence on leisure

Two views of AI in leisure and the work-place and two views of society are discussed. There is a conceptualisation of AI systems enhancing people in their work and leisure and another of AI automata which tends to degrade and replace human activity. Researchers tend to resolve into Optimists who work within a micro-sociological view and see AI systems as inevitable and beneficent. Others are Pessimists who adopt a macro-sociological view and see AI in its automata role and deliterious social consequences. These polarised perspectives must be integrated as only enhancing AI is socially acceptable.     

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.     

Recognition of handwritten musical notes by a modified Neocognitron

A neural network for recognition of handwritten musical notes, based on the well-known Neocognitron model, is described. The Neocognitron has been used for the what pathway (symbol recognition), while contextual knowledge has been applied for the where (symbol placement). This way, we benefit from dividing the process for dealing with this complicated recognition task. Also, different degrees of intrusiveness in learning have been incorporated in the same network: More intrusive supervised learning has been implemented in the lower neuron layers and less intrusive in the upper one. This way, the network adapts itself to the handwriting of the user. The network consists of a 13×49 input layer and three pairs of simple and complex neuron layers. It has been trained to recognize 20 symbols of unconnected notes on a musical staff and was tested with a set of unlearned input notes. Its recognition rate for the individual unseen notes was up to 93%, averaging 80% for all categories. These preliminary results indicate that a modified Neocognitron could be a good candidate for identification of handwritten musical notes.     

Development of an autonomous underwater robot “Twin-Burger” for testing intelligent behaviors in realistic environments

An autonomous underwater robot named Twin-Burger was developed as a versatile test bed to establish the techniques which realize intelligent robot behaviors. The robot was designed to have necessary functions for complex tasks including cooperative task execution with other robots and divers. The first robot Twin-Burger I was completed and launched in November 1992. This paper describes hardware and software systems of the robot. Motion of the robot is controlled by sliding controllers based on simplified equations of motion which are derived from system identification experiments. Tank tests proved that the robot was able to cruise along a commanded path as a sequence of control actions generated by the sliding controllers. The Distributed Vehicle Management Architecture (DVMA) is applied to the robot as an architecture for the control software. Mission execution experiments shows that the Twin-Burger behaves appropriately according to the mission and environmental conditions.     

Virtual Connections and a Traffic Optimization Model for an ATM Network

The number of virtual connections in the nodal space of an ATM network of arbitrary structure and topology is computed by a method based on a new concept—a covering domain having a concrete physical meaning. The method is based on a network information sources—boundary switches model developed for an ATM transfer network by the entropy approach. Computations involve the solution of systems of linear equations. The optimization model used to compute the number of virtual connections in a many-category traffic in an ATM network component is useful in estimating the resource of nodal equipment and communication channels. The variable parameters of the model are the transmission bands for different traffic categories.     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)