An Algorithm to Decide Feasibility of Linear Integer Constraints Occurrng in Decision Tables

Abstract-To detect errors in decision tables one needs to decide whether a given set of constraints is feasible or not. This paper describes an algorithm to do so when the constraints are linear in variables that take only integer values. Decision tables with such constraints occur frequently in business data processing and in nonnumeric applications. The aim of the algorithm is to exploit. the abundance of very simple constraints that occur in typical decision table contexts. Essentially, the algorithm is a backtrack procedure where the the solution space is pruned by using the set of simple constrains. After some simplications, the simple constraints are captured in an acyclic directed graph with weighted edges. Further, only those partial vectors are considered from extension which can be extended to assignments that will at least satisfy the simple constraints. This is how pruning of the solution space is achieved. For every partial assignment considered, the graph representation of the simple constraints provides a lower bound for each variable which is not yet assigned a value. These lower bounds play a vital role in the algorithm and they are obtained in an efficient manner by updating older lower bounds. Our present algorithm also incorporates an idea by which it can be checked whether or not an (m - 2)-ary vector can be extended to a solution vector of m components, thereby backtracking is reduced by one component.

Low Complexity LID using Pruned Pattern Tables of LZW

We present two discriminative language modelling techniques for Lempel-Ziv-Welch (LZW) based LID system. The previous approach to LID using LZW algorithm was to directly use the LZW pattern tables forlanguage modelling. But, since the patterns in a language pattern table are shared by other language pattern tables, confusability prevailed in the LID task. For overcoming this, we present two pruning techniques (i) Language Specific (LS-LZW)-in which patterns common to more than one pattern table are removed. (ii) Length-Frequency product based (LF-LZW)-in which patterns having their length-frequency product below a threshold are removed. These approaches reduce the classification score (Compression Ratio [LZW-CR] or the weighted discriminant score [LZW-WDS]) for non native languages and increases the LID performance considerably. Also the memory and computational requirements of these techniques are much less compared to basic LZW techniques.

Validation of Decision Tables Used in Process Control

Process control rules may be specified using decision tables. Such a specification is superior when logical decisions to be taken in control dominate. In this paper we give a method of detecting redundancies, incompleteness, and contradictions in such specifications. Using such a technique thus ensures the validity of the specifications.

Nodal domains of the equilateral triangle billiard

We characterize the eigenfunctions of an equilateral triangle billiard in terms of its nodal domains. The number of nodal domains has a quadratic form in terms of the quantum numbers, with a non-trivial number-theoretic factor. The patterns of the eigenfunctions follow a group-theoretic connection in a way that makes them predictable as one goes from one state to another. Extensive numerical investigations bring out the distribution functions of the mode number and signed areas. The statistics of the boundary intersections is also treated analytically. Finally, the distribution functions of the nodal loop count and the nodal counting function are shown to contain information about the classical periodic orbits using the semiclassical trace formula. We believe that the results belong generically to non-separable systems, thus extending the previous works which are concentrated on separable and chaotic systems.