Enumeration of Optimal Ternary Constant-Composition Codes

The problem of classification of optimal ternary constant-composition codes is considered. Using a combinatorial-computer method, the number of inequivalent codes is determined for 3 d n 10.     

Pushing Convertible Constraints in Frequent Itemset Mining

Recent work has highlighted the importance of the constraint-based mining paradigm in the context of frequent itemsets, associations, correlations, sequential patterns, and many other interesting patterns in large databases. Constraint pushing techniques have been developed for mining frequent patterns and associations with antimonotonic, monotonic, and succinct constraints. In this paper, we study constraints which cannot be handled with existing theory and techniques in frequent pattern mining. For example, avg(S)v, median(S)v, sum(S)v (S can contain items of arbitrary values, {<, <, , } and v is a real number.) are customarily regarded as tough constraints in that they cannot be pushed inside an algorithm such as Apriori. We develop a notion of convertible constraints and systematically analyze, classify, and characterize this class. We also develop techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining. Results from our detailed experiments show the effectiveness of the techniques developed.     

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.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

Unary Quantifiers on Finite Models

In this paper (except in Section 5) all quantifiers are assumedto be so called simple unaryquantifiers, and all models are assumedto be finite. We give a necessary and sufficientcondition for a quantifier to be definablein terms of monotone quantifiers. For amonotone quantifier we give a necessaryand sufficient condition for beingdefinable in terms of a given set of bounded monotonequantifiers. Finally, we give a necessaryand sufficient condition for a monotonequantifier to be definable in terms of agiven monotone quantifier.Our analysis shows that the quantifierat least one half and its relatives behavedifferently than other monotone quantifiers.     

An extension of the theory of learning systems

Summary The author's inquiry [1] on learning systems is generalized in the following respects: The process of learning, instead of coming to an end when the learning goal has been reached, is supposed to last for ever, so that the above definitive learning as well as phenomena such as forgetting, re-learning, changing the goal etc. become describable.We take over the notion of semi-uniform solvability of a set of learning problems (2.2), but now (trivial cases excluded) the whole capacity of a learning system is never s. u. solvable. Finite such sets are. The notion of a solving-basis of some is introduced and we can state necessary conditions that possess such a basis (2.14), so that examples of sets without a basis can be provided. On the other hand, any s. u. solvable has as basis. The notion of uniform solvability (3.1) reinforces that of s. u. solvability, and there are given sufficient conditions for to be uniformly solvable (3.6). In some finite cases, s. u. solvability, existence of a basis and uniform solvability coincide (3.7–3.9). At last we give the construction for the weakest learning system solving a uniformly solvable problem set (3.12–3.19).Eine deutsche Fassung wurde am 30. Mai 1972 eingereicht.     

Indecomposable local maps of tessellation automata

Indecomposable local maps of one-dimensional tessellation automata are studied. The main results of this paper are the following. (1) For any alphabet containing two or more symbols and for anyn 1, there exist indecomposable scope-n local maps over . (2) If is a finite field of prime order, then a linear scope-n local map over is indecomposable if and only if its associated polynomial is an irreducible polynomial of degreen – 1 over , except for a trivial case. (3) Result (2) is no longer true if is a finite field whose order is not prime.     

Multimedia teleorchestra with independent sources: Part 1 — temporal modeling of collaborative multimedia scenarios

Multimedia synchronization involving independent sources is a challenging issue imposed by the distributed multimedia applications. In our work, this issue is studied by investigating the teleorchestra application (remote multimedia presentation). In teleorchestration, among the data objects to be presented, relative and uncertain temporal requirements may be involved. Fuzzy presentation scenarios are thus generated. In this paper, we describe a temporal model that can handle these fuzzy scenarios that contain imprecise synchronization constraints, such as unknown object presentation durations and relative event occurring times. The model supports a distributed synchronization algorithm that can schedule the independent sources for the multimedia teleorchestration.     

Bursty and Hierarchical Structure in Streams

A fundamental problem in text data mining is to extract meaningful structure from document streams that arrive continuously over time. E-mail and news articles are two natural examples of such streams, each characterized by topics that appear, grow in intensity for a period of time, and then fade away. The published literature in a particular research field can be seen to exhibit similar phenomena over a much longer time scale. Underlying much of the text mining work in this area is the following intuitive premise—that the appearance of a topic in a document stream is signaled by a burst of activity, with certain features rising sharply in frequency as the topic emerges.The goal of the present work is to develop a formal approach for modeling such bursts, in such a way that they can be robustly and efficiently identified, and can provide an organizational framework for analyzing the underlying content. The approach is based on modeling the stream using an infinite-state automaton, in which bursts appear naturally as state transitions; it can be viewed as drawing an analogy with models from queueing theory for bursty network traffic. The resulting algorithms are highly efficient, and yield a nested representation of the set of bursts that imposes a hierarchical structure on the overall stream. Experiments with e-mail and research paper archives suggest that the resulting structures have a natural meaning in terms of the content that gave rise to them.     

Information and pragmatic value-adding: Language games and information science

This paper discusses terms which are of mutual importance to the fields of information science and computer science. Specifically we discuss the notions of information and knowledge: their interrelationships as well as their differences, and the concept of value-adding. Concrete examples are used in the discussion.Rainer Kuhlen is professor of Information Science at the University of Konstanz.     

Partial Evaluation of Views

Many database applications and environments, such as mediation over heterogeneous database sources and data warehousing for decision support, lead to complex queries. Queries are often nested, defined over previously defined views, and may involve unions. There are good reasons why one might want to remove pieces (sub-queries or sub-views) from such queries: some sub-views of a query may be effectively cached from previous queries, or may be materialized views; some may be known to evaluate empty, by reasoning over the integrity constraints; and some may match protected queries, which for security cannot be evaluated for all users.In this paper, we present a new evaluation strategy with respect to queries defined over views, which we call tuple-tagging, that allows for an efficient removal of sub-views from the query. Other approaches to this are to rewrite the query so the sub-views to be removed are effectively gone, then to evaluate the rewritten query. With the tuple tagging evaluation, no rewrite of the original query is necessary.We describe formally a discounted query (a query with sub-views marked that are to be considered as removed), present the tuple tagging algorithm for evaluating discounted queries, provide an analysis of the algorithm's performance, and present some experimental results. These results strongly support the tuple-tagging algorithm both as an efficient means to effectively remove sub-views from a view query during evaluation, and as a viable optimization strategy for certain applications. The experiments also suggest that rewrite techniques for this may perform worse than the evaluation of the original query, and much worse than the tuple tagging approach.     

CLSS: An Intelligent Crane Lorry Scheduling System

Companies that provide crane-lorry services are faced with the daily need to perform vehicle and driver allocation and scheduling. Many companies still do this manually due to the lack of suitable technologies. This manual approach is both time consuming and inaccurate and most probably will not lead to an optimized plan that can reduce operational costs. In this paper, we describe the design of a system called Crane Lorry Scheduling System (CLSS) that we have developed for the largest crane lorry company in Hong Kong. A crane lorry company is a company that provides lorries with different types of mounted crane equipment and drivers to service different types of moving and lifting jobs. CLSS is a Web-based application that streamlines communication with customers, subcontractors and employees/lorry drivers. We modeled the lorry-assignment problem as a constraint-satisfaction problem (CSP) algorithm, which we call the Crane Lorry Optimizing Engine (CLOE). CLOE was designed to be easily customizable to match the needs and requirements of different crane lorry companies. We experimented with two versions of CLOE, regular CLOE that finds best solutions and X-CLOE that finds optimal solutions. Results from our tests show that CLOE is faster and generates better quality plans than the manual approach.     

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.     

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.     

An environment to support micro-incremental class development

Incremental development and testing is widely cited as one advantage of the object-oriented paradigm. To date, most of the work in this area emphasizes incremental development at the macro level, i.e., at the application or class hierarchy levels. We believe that incremental development should also be exploited at the individual class level. In particular, classes may contain a variety of methods that place objects of the class into relatively complex states. By organizing and developing an individual class in an incremental fashion, one can (a) develop and test partial classes and (b) generate simple states for test objects prior to generating more complex ones. This process realizes two benefits: it simplifies debugging by reducing the size of the search space when tracking down defects, and it makes regression testing more efficient. This paper reports on a development environment designed to support micro-incremental class development. This environment integrates several different components and techniques. We discuss each component of the environment individually, and then illustrate the use of the environment in a case study.     

Ü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.

     

Transformation of programs for fault-tolerance

In this paper we describe how a program constructed for afault-free system can be transformed into afault-tolerant program for execution on a system which is susceptible to failures. A program is described by a set of atomic actions which perform transformations from states to states. We assume that a fault environment is represented by a programF. Interference by the fault environmentF on the execution of a programP can then be described as afault-transformation which transformsP into a program (P). This is proved to be equivalent to the programPP _F , whereP _F is derived fromP andF, and defines the union of the sets of actions ofP andF _P . A recovery transformation transformsP into a program (P) =PR by adding a set ofrecovery actions R, called arecovery program. If the system isfailstop and faults do not affect recovery actions, we have ((P))=(P)R=PP _F R We illustrate this approach to fault-tolerant programming by considering the problem of designing a protocol that guarantees reliable communication from a sender to a receiver in spite of faults in the communication channel between them.     

Beyond Market Baskets: Generalizing Association Rules to Dependence Rules

One of the more well-studied problems in data mining is the search for association rules in market basket data. Association rules are intended to identify patterns of the type: A customer purchasing item A often also purchases item B. Motivated partly by the goal of generalizing beyond market basket data and partly by the goal of ironing out some problems in the definition of association rules, we develop the notion of dependence rules that identify statistical dependence in both the presence and absence of items in itemsets. We propose measuring significance of dependence via the chi-squared test for independence from classical statistics. This leads to a measure that is upward-closed in the itemset lattice, enabling us to reduce the mining problem to the search for a border between dependent and independent itemsets in the lattice. We develop pruning strategies based on the closure property and thereby devise an efficient algorithm for discovering dependence rules. We demonstrate our algorithm's effectiveness by testing it on census data, text data (wherein we seek term dependence), and synthetic data.     

Geometrical Method of Scheduling in Project Management

Consideration was given to scheduling by the criterion for uniform use of resources. It was assumed that each job is executed by a unit resource. Two types of inter-job dependences were studied: finish–finish (one job cannot be completed until the other is completed) and finish–start (one job cannot be started until the other is not completed). To solve the problem, a geometrical method reducing solution to determining the shortest trajectory in a domain constructed from the network graph was proposed.     

Types with intersection: An introduction

This paper is an informal introduction to the theory of types which use a connective for the intersection of two types and a constant for a universal type, besides the usual connective for function-types. This theory was first devised in about 1977 by Coppo, Dezani and Sallé in the context of-calculus and its main development has been by Coppo and Dezani and their collaborators in Turin. With suitable axioms and rules to assign types to-calculus terms, they obtained a system in which (i) the set of types given to a term does not change under-conversion, (ii) some interesting sets of terms, for example the solvable terms and the terms with normal form, can be characterised exactly by the types of their members, and (iii) the type-apparatus is not so complex as polymorphic systems with quantifier-containing types and therefore probably not so expensive to implement mechanically as these systems.There are in fact several variant systems with different detailed properties. This paper defines and motivates the simplest one from which the others are derived, and describes its most basic properties. No proofs are given but the motivation is shown by examples. A comprehensive bibliography is included.