%U http://www.cse.buffalo.edu/tech-reports/90-12.ps %A Rapaport, W. %T Cognitive Science (Superseded by TR 96-19) %R 90-12 %D May 1990 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/90-24.ps %A He, X. %T On Finding the Rectangular Duals of Planar Triangulated Graphs %R 90-24 %D September 1990 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-04.ps %A Homer, S. %A Selman, A. %T Complexity Theory %R 91-04 %D June 8, 1992 %I Department of Computer Science, SUNY Buffalo %X This is an introductory survey of complexity theory. Topics covered include Modes of Computation, Complexity Classes and Complexity Measures, Basic Results, Nondeterminism and NP-Completeness, Relative Computability, Parallelism, Probabilistic Complexity Classes, and Structural Complexity Theory. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-05.ps %A He, X. %T Efficient Parallel Algorithms for Two Graph Layout Problems %R 91-05 %D June 1991 %I Department of Computer Science, SUNY Buffalo %X We present efficient parallel algorithms for solving two graph layout problems: Find a F$\acute{a}$ry Embedding on a grid and construct a rectangular dual for planar graphs. The algorithm for the first problem takes $O(\log\em{n}\log^*\em{n})$ time with $O(n)$ processors on a PRAM. The algorithm for the second problem takes $O(\log^2\em{n})$ time with $O(n)$ processors. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-09.ps %A Haas, J. %A Jayaraman, B. %T Automatic Synthesis of Semantics for Context-free Grammars %R 91-09 %D July 1991 %I Department of Computer Science, SUNY Buffalo %X We are investigating the mechanical transformation of an unambiguous context-free grammar (CFG) into a definite-clause grammar (DCG) using a finite set of examples, each of which is a pair $\langle s,~m\rangle$, where $s$ is a sentence belonging to the language defined by the CFG and $m$ is a semantic representation (meaning) of $s$. The resulting DCG would be such that it can be executed (by the interpreter of a logic programming language) to compute the semantics for every sentence of the original DCG. Three important assumptions underlie our approach: (i) the semantic representation language is the {\it simply typed $\lambda$-calculus}; (ii) the semantic representation of a sentence can be obtained from the semantic representations of its parts ({\it compositionality}); and (iii) the structure of the semantic representation determines its meaning ({\it intensionality}). The basic technique involves an enumeration of parse trees for sentences of increasing size; and, for each parse tree, a set of equations over (typed) function variables that represent the meanings of the constituent subtrees is formulated and solved by means of a higher-order unification procedure. The solutions for these function variables serve to augment the original grammar in order to derive the final DCG. A technique called {\it partial execution} is used to convert, where possible, the generated higher-order DCG into a first-order DCG, to facilitate efficient bidirectional execution. In the appendix, we provide detailed illustration of the use of such a system for storing and retrieving information contained in natural language sentences. Based on our experimentation, we conclude that an improved version of this system will facilitate rapid prototyping of natural language front-ends for various applications. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-11.ps %A Jayaraman, B. %T The SuRE Programming Framework %R 91-11 %D August 1991 %I Department of Computer Science, SUNY Buffalo %X The goal of this work is the design of logic programming constructs that will help minimize the dependence on extralogical features. Towards this end, we explore in this paper three forms of logical assertions---equational, relational, and subset assertions---accompanied by corresponding matching and unification operations. The uses of equations and relations are well-known, and hence we concentrate on the uses of the subset assertion. In an earlier paper, we introduced three forms of this assertion: $f(terms) \supseteq expr$, $f(terms) \supseteq set$, and $f(terms) \supseteq set$ {\tt :-} {\it condition}. In this paper, we show how subset assertions can be used to re-formulate a relation as a set-valued function, thereby declaratively specifying which arguments of the relation are the input arguments and thus obviating {\it mode} declarations. We also present two new ways of invoking a function defined by subset assertions: using an element goal, $f(terms) \ni x$, to incrementally generate elements; and using a superset goal, $f(terms) \supseteq s$, to lazily generate the entire set. We show how lazy generation of the set allows the search space to be pruned declaratively, obviating some uses of the {\it cut}, while eager generation of the set corresponds to the {\it setof} construct of Prolog. Subset assertions can also help efficiently formulate transitive-closure operations, which are traditionally expressed using {\it assert} and {\it retract}. In this paper, we also consider the respective duals of the foregoing three forms of subset assertions: $f(terms) \subseteq expr$, $f(terms) \subseteq set$, and $f(terms) \subseteq set$ {\tt :-} {\it condition}. We show that these new logical forms also have very natural uses, especially in flow analysis problems. The programming framework embodying all these features is called {\bf SuRE}---for {\bf Su}bsets, {\bf R}elations, and {\bf E}quations---and is being implemented with a view to answer the question: can logic programming be declarative and practical? Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-12.ps %A Selman, A. %T A Taxonomy of Complexity Class of Functions %R 91-12 %D June 1992 %I Department of Computer Science, SUNY Buffalo %X This paper comprises a systematic comparison of several complexity classes of functions that are computed nondeterministically in polynomial time or with an oracle in NP. There are three components to this work. - A taxonomy is presented that demonstrates all known inclusion relations of these classes. For (nearly) each inclusion that is not shown to hold, evidence is presented to indicate that the inclusion is false. As an example, consider FewPF, the class of multivalued functions that are nondeterministically computable in polynomial time such that for each {\em x}, there is a polynomial bound on the number of distinct output values of $f(x)$. We show that ${\rm FewPF} \subseteq {\rm PF}^{{\rm NP}}_{tt}$. However, we show ${\rm PF}^{{\rm NP}}_{tt} \subseteq $ FewPF if and only if NP = co-NP, and thus ${\rm PF}^{{\rm NP}}_{tt} \subseteq {\rm FewPF}$ is likely to be false. - Whereas it is known that ${\rm P}^{{\rm NP}}(O(\log n)) = {\rm P}^{{\rm NP}}_{tt} \subseteq{\rm P}^{{\rm NP}}$ [Hem87, Wagb, BH88], we show that ${\rm PF}^{{\rm NP}}(O(\log n)) ={\rm PF}^{{\rm NP}}_{tt}$ implies P = FewP and R = NP. Also, we show that ${\rm PF}^{{\rm NP}} _{tt} = {\rm PF}^{{\rm NP}}$ if and only if ${\rm P}^{{\rm NP}}_{tt} ={\rm P}^{{\rm NP}}$. - We show that if every nondeterministic polynomial-time multivalued function has a single-valued nondeterministic refinement (equivalently, if every honest function that is computable in polynomial-time can be inverted by a single-valued nondeterministic function), then there exists a disjoint pair of NP-complete sets such that every separator is NP-hard. The latter is a previously studied open problem that is closely related to investigations on promise problems. This results motivates a study of reduction between partial multivalued functions. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-13.ps %A Shapiro, S. %A Chalupsky, H. %A Chou, H. %T Connecting ARC/INFO and SNACTor Project Report %R 91-13 %D June 1992 %I Department of Computer Science, SUNY Buffalo %X This report describes an interface between ARC/INFO, a geographic information management system, and SNACTor, the SNePS acting component. It also shows a small example interaction that demonstrates how ARC/INFO and SNACTor can interact using the new interface, and how more sophisticated future applications can make use of its functionality. The interface was designed and implemented during a two-month research project carried out in Summer, 1990 at the State University of new York at Buffalo. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-14.ps %A Shende, A. %T Digital Analog Simulation of Uniform Motion in Representations of Physcial N-Space by Lattice-work MIMD Computer Architectures %R 91-14 %D April 1991 %I Department of Computer Science, SUNY Buffalo %X This doctoral dissertation is part of an ongoing research project with John Case, Dayanand S. Rajan and myself. We are investigating the possibility of solving problems in scientific computing involving the motion of objects in a bounded region of physical {\em n}-space by (a) representing points in the region of space by processors in a lattice-work mesh of processors with local connections for inter-processor communication, and (b){\em literally, analogically} simulating the motion of objects by representing the particles of these objects by algorithms which move themselves about in the lattice-work processors, much as the motion in real space of the particles making up real objects, in effect, constitutes the motion of those objects. The main contributions of this dissertation are (i) two provably correct algorithms to generate {\em virtually perfectly shaped} spherical wavefronts emanating from a point source at virtually constant radial speed, (ii) a provably correct algorithm template for simulating the unform-speed traversal of certain curves by a single particle, and (iii) for the two algorithms of (i) and the template of (ii), the specification of classes of meshes which are excellent discrete approximations to bounded regions of euclidean {\em n}-space, and on which these algorithms can be executed. Algorithms for the simulation of uniform-speed translation and uniform angular speed revolution of single particles are presented as specific instances of the algorithm template. A {\em crucial} aspect of {\em all} the algorithms in this dissertation is that, in spite of the discreteness of the representation of physical {\em n}-space, the {\em speed} of the simulations, using these algorithms, is approximately {\em linearly proportional} to the speed of the phenomenon being simulated. Furthermore, all decisions made by processors running these algorithms are based only on {\em local} information, such as messages from neighboring processors. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-16.ps %A He, X. %T Parallel Algorithm for Cograph Recognition with Applications (Revised) %R 91-16 %D June 1991 %I Department of Computer Science, SUNY Buffalo %X We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes $O(\log^2 n)$ time with $O(n+m)$ processors on a CRCW PRAM, where $n$ and $m$ are the number of vertices and edges of the graph. Using cotree representation, we obtain parallel algorithms for solving the maximum matching and the permutation representation problems for cographs using $O(\log n)$ time with $O(n)$ processors. We also obtain a parallel algorithm for the depth-first spanning tree problem for permutation graphs (a class properly contains cographs) which takes $O(\log^2 n)$ time with $O(n)$ processors. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/91-18.ps %A Regan, K. %A Schwentick, T. %T On the Power of One Bit of a Number-P Function %R 91-18 %D June 5, 1992 %I Department of Computer Science, SUNY Buffalo %X We introduce the class $MP$ of languages $L$ which can be solved in polynomial time with an oracle for one selected bit of the value $f(y)$ of a $\# P$ function $f$ on a selected argument $y$. This extends the much-studied language classes $\oplus P$ and $PP$, which correspond to the power of the least and most significant bits, respectively. We show that $MP$ is captured by the power of the middle bit; namely: a language $L$ is in $MP$ iff for some $\# P$ function $f'$ and all $x$, $x \in L \iff$ the middle bit of $f'(x)$ in binary notation is a `1'. Also, S.~Toda's proof [Toda89,91] that the polynomial hierarchy ($PH$) is contained in $P^{\# P}$ actually gives: $PH \subseteq BP[\oplus P] \subseteq C \oplus P \subseteq MP$. The class $MP$ has complete problems, and is closed under complements and under polynomial-time many-one reducibility. We show that $MP$ is closed under intersection iff, for any fixed $k > 0$, $k$ bits of a $\# P$ function are no more powerful than one. Moreover, if there is a polynomial-time construction for the closure under intersection, then $O(\log n)$-many bits have the same power as one. We examine the subclass $AmpMP$ of languages whose $MP$ representations can be ``amplified,'' showing that $BP[\oplus P] \subseteq AmpMP$, and that for any subclass $\cal C$ of $AmpMP$ which is closed under polynomial-time many-one reducibility, $MP^{\cal C} = MP$. Hence $BP[\oplus P]$ is low for $MP$, and if $C_{=}P \subseteq AmpMP$, then $PP^{PP} = MP$. Finally, our work leads to a purely mathematical question about the size of integer-valued polynomials $p(x,y)$ which satisfy certain congruence relations, one which also matters to the theory of bounded-depth circuits. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-03.ps %A Revankar, S. %A Sher, D. %T Supervised Image Segmentation %R 92-03 %D January 1992 %I Department of Computer Science, SUNY Buffalo %X Image segmentation is a process of dividing an image into meaningful regions. Human supervision of computer generated segmentation is essential for the tasks such as medical image analysis, surveillance-radar image analysis, etc. The decisions to be made based on the segmented images is often critical in such domains, and neither human imprecision nor the unreliability of automatic algorithms is tolerable. We develop a collaborative scheme that facilitates active human supervision of computer segmentation of images. Through this, we complement the reliability of a human expert with the precision of segmentation and deformable modeling algorithms that track a stationary or moving nonrigid object in a sequence of snap-shots of the scene. In our system, an expert user observes the computer generated segmentaion along with the original images in a user friendly graphics environment, and interactively indicates the wrongly classified regions either by {\it pointing} or by {\it circling.} The precise boundaries of indicated regions are computed by studying original image properties at that region, and the human visual {\it attention distribution map} obtained from the published psychological and psychophysical research. All refinement operations are defined in the form of a linear functions so that the facilities such as error recovery, commutativity of operations, etc. are inherent to the system. We use the developed theory to extract heart walls from a sequence of two dimensional echocardiograms. Echocardiography is one of the most popular and safest methods of observing the heart. Segmentation of the heart wall in echocardiograms is essential to detect and quantize a large spectrum of heart abnormalities. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-09.ps %A Chuang, E. %A Sher, D. %T Chi-square Tests for Feature Detection %R 92-09 %D May 1992 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-10.ps %A Chuang, E. %A Sher, D. %T Evidence Representation & Combination in Low-level Vision %R 92-10 %D May 1992 %I Department of Computer Science, SUNY Buffalo %X We discuss using statistics from $\chi^{2}$ tests and summing rule$^{(1)}$ for evidence representation and combination in low-level vision. Feature likelihoods are represented by statistics which are assured from $\chi^{2}$ tests, and the relationship between these likelihoods and noise level is linear. Multiple statistics are combined by summing rule into statistics for larger features such as segments and polygons. This is justified because the sum on a set of independent $\chi^{2}$ random variables is also a $\chi^{2}$ random variable, and the geometric meaning of the sum is equal to the integration of these addends. Examples show that the performance of Hough transform for detecting line segments is significantly improved if statistics are included. Therefore, statistics which adopted as evidence can not only include uncertainty, but also help to avoid error in Hough transform. The summing rule can combine statistics from $\chi^2$ tests, and also can integrate the meanings of addends into the sum. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-12.ps %A Ho, Tin Kam %T A Theory of Multiple Classifier Systems and Its Application to Visual Word Recognition %R 92-12 %D May 1992 %I Department of Computer Science, SUNY Buffalo %X Despite the success of many pattern recognition systems in constrained domains, problems that involve noisy input and many classes remain difficult. A promising direction is to use several classifiers simultaneously, such athat they can complement each other in correctness. This thesis is concerned with decisions combination in a multiple classifer system that is critical to its success. A multiple classifer system consists of a set of a set of classifers and a decision combination function. It is a preferred solution to a complex recognition problem because it allows simultaneous use of feature descriptors of many types, corresponding measures of similarity, and many classification procedures. It also allows dynamic selection, so that classifiers adapted to inputs of a particular type many be applied only when those inputs are encountered. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-13.ps %A Revankar, S. %A Sher, D. %T Pattern Extraction by Adaptive Propagation of a Regional Threshold %R 92-13 %D June 1992 %I Department of Computer Science, SUNY Buffalo %X We describe a mehtod for pattern extraction by adaptive propogation of regional threshold to the rest of the image. In most imageds there is an easily thresholded region. We propagate the regional threshold to the entire image using a linear approximation of the image intensity gradients. This method is useful in the fields where the extraction of precise geometry of the binarized patterns is required, and in the fileds where continuous thin lines are to be extracted. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-14.ps %A Khoubyari, S. %T The Application of Word Image Matching in Text Recogntion %R 92-14 %D June 1992 %I Department of Computer Science, SUNY Buffalo %X Printed text recognition usually involves recognizing individual characters, and assembling the results to recognize words and sentences. However, the performance of conventional character recognition systems tends to suffer in the presence of moderate levels of deradation in the text. A method is proposed that uses equivalence among frequent word images to derive hypotheses for each word using the available language statistics. Word images are clustered to determine equivalency. The attributes of the clusters, as well as the relationships among them matched with the same characteristics for the words in the language. The method requires no explicit training, and is fairly tolerant to image degradation. The results for several sample sizes are reported. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-18.ps %A Sunder, S. %A He, X %T An NC Algorithm for Finding Minimum Weighted Completion Time Schedule on Series Parallel Graphs %R 92-18 %D July 1992 %I Department of Computer Science, SUNY Buffalo %X We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes $O(\log^2 n)$ time with $O(n^3)$ processors on a CREW PRAM, where $n$ is the number of vertices of the input graph. This is the first NC algorithm for solving the problem. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-21.ps %A Hexmoor, H. %A Lammens, J. %A Shapiro, S. %T An Autonomous Agent Architecture for Integrating Perception and Acting with Grounded Embodied Symbolic Reasoning %R 92-21 %D August 1992 %I Department of Computer Science, SUNY Buffalo %X We describe an agent architecture in terms of general principles of organization of components for an autonomous agent that functions in the world. The architecture is described independent of computational components of the agent that are used to generate behavior. It specifies an integration of explicit representation and reasoning mechanisms, embodied semantics through grounding symbols in perception and action, mechanisms for finding and maintaining a correspondence between symbols and sensory-perceived objects, and implicit representation of special-purpose mechanisms of sensory processing, perception, and motor control for the agent. We then present components that we place in our general architecture to build an agent that exhibits situated activity and learning. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-22.ps %A Milun, D. %A Sher, D. %T Improving Edge Detectors on Compressed Images-A Trainable Markov Random Field Approach %R 92-22 %D September 1992 %I Department of Computer Science, SUNY Buffalo %X We use Markov random fields to improve the output of the thinned Sobel edge detector, applied to images compressed using the JPEG technique. JPEG compression saves a lot of file space, however it introduces correlated errors into the images. This is exactly a circumstnace for which our recently developed double neighborhood MRFs are suited (Milun and Sher, 1992a). Double neighborhood MRFs are constructed by sampling from pairs of original images together with noisy imagery This models the noise within the MRF probability density function without having to make assumptions about its form. This provides an easy to generate Markov random fields for annealing or other relaxation methods. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-24.ps %A Jagota, A. %A Regan, K. %T Performance of MAX-CLIQUE Approximation Heuristics Under Description-Length Weighted Distributions %R 92-24 %D October 1992 %I Department of Computer Science, SUNY Buffalo %X We study the average performance of several neural-net heuristics applied to the problem of finding the size of the largest clique in an undirected graph. This function is NP-hard even to approximate within a constant factor in the worst case [S.~Arora, C.~Lund, et.al., FOCS '92], but the heuristics we study are known to do quite well on average for instances drawn from the uniform distribution on graphs of size $n$. We extend a theorem of M. Li and P. Vitanyi [Info. Proc. Lett. 5/92] to show that for instances drawn from the {\em universal distribution\/} m(x), the average-case performance of any approximation algorithm has the same order as its worst-case performance. The universal distribution is not computable or samplable. However, we give a realistic analogue q(x) which lends its elf to efficient empirical testing. Our results so far are: out of nine heuristics we tested, three did markedly worse under q(x) than under uniform distribution, but six others revealed little change. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-25.ps %A Revankar, S. %A Sher, D. %T Constrained Contouring in the Polar Coordinates %R 92-25 %D October 1992 %I Department of Computer Science, SUNY Buffalo %X A constrained contour is an outline of a region of interest, obtained by linking edges under the constraints of connectivity, smoothness, image context and subjective or user specified constraints. We discuss a constrained contouring algorithm in polar coordinates to trace closed contours. The algorithm finds optimal contour locations in all radial direction according to the constraintsof context, distance from approximate contour and the image gradient. These optimal edge-points ordered according to their angular coordinates. We treat these edge points as the nodes of a graph of all possible contours. The links of the graph are weighted so that the shortest path between a poir of nodes is the smooth contour that traces maximum number of edge-points, and the shortest cycle in the graph gives the optimal contour. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-26.ps %A Chakravarty, S. %A Gong, Y. %T An Algorithm for Diagnosing Two-Line Bridging Faults in Combinational Circuits %R 92-26 %D October 1992 %I Department of Computer Science, SUNY Buffalo %X A novel algorithm for diagnosing all {\em Two-Line Bridging Faults} in Combinational Circuits is presented. It assumes the {\em Wired-OR (Wired-AND)} model and uses: SOPS to represent the set of possible bridging faults making it space efficient; and a set of rules for dropping faults from the set of possible faults. The rules use {\em fault dictionaries}, not for bridging faults but, for {\em stuck-at} faults only. Experimental results point to: the computational feasibility of considering all two-line bridging faults while diagnosing combinational circuits; and the effectiveness of the algorithm. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-27.ps %A Green, F. %A Kobler, J. %A Regan, K. %A Schwentick, T. %A Toran, J. %T The Power of the middle Bit of Number-P Function %R 92-27 %D October 1992 %I Department of Computer Science, SUNY Buffalo %X We introduce the class MP of languages $L$ which can be solved in polynomial time with the additional information of one bit from a $\#$P function $f$. We prove that the polynomial hierarchy and the classes $\mbox{\it Mod}_k\mbox{P}$, $k\geq2$, are low for this class. We show that the middle bit of $f(x)$ is as powerful as any other bit, and that a wide range of bits around the middle have the same power. By contrast, the $O(\log n)$ many least significant bits are equivalent to $\oplus$P [R.~Beigel, J.~Gill, and U.~Hertrampf, 1990], and we show that the $O(\log n)$ many most significant bits are equivalent to PP; hence these bits are probably weaker. We study also the subclass AmpMP of languages whose MP representations can be ``amplified,'' showing that $\mbox{BPP}^{\oplus{\mbox{P}}}\subseteq \mbox{AmpMP}$, and that important subclasses of AmpMP are low for MP. We translate some of these results to the area of circuit complexity using MidBit (middle bit) gates. A MidBit gate over $w$-many inputs $x_1,\dots,x_w$ is a gate which outputs the value of the $\lfloor\log(w)/2\rfloor^{\rm th}$ bit in the binary representation of the number $\sum_{i=1}^wx_i$. We show that every language in ACC can be computed by a family of depth-2 deterministic circuits of size $2^{(\log n)^c}$ with a MidBit gate at the root and AND-gates of fan-in $(\log n)^c$ at the leaves. This result improves the known upper bounds for the class ACC. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-30.ps %A Sher, David B. %A Cheung, Chris Y. %T Constructing Noise-Reducing Operators from Training Images %R 92-30 %D November 1992 %I Department of Computer Science, SUNY Buffalo %X We discuss constructing non-linear noise reduction images. We extract from the training set a probability distribution over local neighborhoods. Our operator changes pixel values when such a change turns a low probability neighborhood into high probability one. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-32.ps %A Chakravarty, S. %A Theophilopoulos, G. %T Computing Robust Test for Stuck-open Faults from Stuck-at Test Sets %R 92-32 %D December 1992 %I Department of Computer Science, SUNY Buffalo %X An experimental system for computing robust tests for stuck-open faults in static CMOS circuits is presented. It constructs robust test-pairs from tests for stuck-at faults by identifying several classes of FETs. Robust tests for stuck-open faults in FETs belonging to these classes are constructed from any stuck-at test set by carefully constructing initialization vectors. Initialization vectors are constructed by examining the "parity" of the paths in the circuit. Robust tests for additional faults are identified using stuck-open fault simulaton. Experimental results show that the system can compute robust tests for a "very large" percentage of the stuck- open faults in a "reasonable" time. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-33.ps %A Jagota, A. %T Approximating Maximum Clique with a Hopfield Network %R 92-33 %D December 1992 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-01.ps %A Sarnath, R. %T Doubly logarithmic time parallel sorting %R 93-01 %D January 1993 %I Department of Computer Science, SUNY Buffalo %X Recently, attempts have been made to separate the problem of parallel sorting from that of list ranking, in order to get around the well known $\Omega (\log n/\log \log n)$ lower bound. These approaches have been of two kinds - {\em chain sorting} and {\em padded sorting}. Here we present nearly optimal, comparison based {\em padded} sorting algorithms that run in average case time $O(\frac{1}{\epsilon ^2} + \frac{1}{\epsilon } \log \log n)$ using $n^{1+\epsilon }$ processors, and $O(n^{1+\epsilon })$ space, on an Common CRCW PRAM.From these results, algorithms for {\em chain sorting} within the same time and processor bounds can be easily obtained. Using a similar approach, we also give an $O(1)$ average case time, comparison based algorithm for finding the largest of $n$ items using a linear number of processors. The algorithm for finding the maximum, runs on a Common CRCW PRAM using only $n^{3/4}$ cells of shared memory. Finally, we obtain randomised algorithms for these problems that run on Common/Tolerant CRCW PRAMs, and also satisfy the above time and processor bounds. As a consequence of our results on sorting, we can also show that the problem of sorting arbitrary input sequences can be reduced to that of sorting integer inputs, within the above mentioned time and processor bounds. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-02.ps %A Sarnath, R. %T Lower bounds for padded sorting and approximate counting %R 93-02 %D January 1993 %I Department of Computer Science, SUNY Buffalo %X We examine the relationship between running time and error of parallel sorting algorithms. This is done by applying Hastad's main lemma to relate the size depth and error of simple circuits, that sort an input of 0's and 1's. As a consequence, we obtain lower bounds for approximate counting as well. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-04.ps %A Chakravarty, Sreejit %A Sivaprakasm, Suresh %T I_DDQ Measurement Based Diagnosis of Bridging Faults in Full %R 93-04 %D February 1993 %I Department of Computer Science, SUNY Buffalo %X An algorithm for diagnosing two node bridging faults in static CMOS combinational circuits(full scan circuits) is presented. This algorithm uses results from $I_{DDQ}$ testing. The bridging faults considered can be between nodes that are outputs of a gate or internal nodes of a gates. Experimental results on all the ISCAS89 circuits show that $I_{DDQ}$ measurement based diagnosis using a small number of randomly generated vectors, is very effective. Moreover, it is computationally feasible to diagnose such a large number of bridging faults when $I_{DDQ}$ measurement is used. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-05.ps %A Fenner, Stephen %A Homer, Steve %A Ogiwara, Mitsunori %A Selman, Alan L. %T On Using Oracles That Compute Values %R 93-05 %D February 17, 1993 %I Department of Computer Science, SUNY Buffalo %X This paper focuses on complexity classes of partial functions that are computed in polynomial time with oracles in NPMV, the class of all multivalued partial functions that are computable nondeterministically in polynomial time. Concerning deterministic polynomial-time reducibilities, it is shown that \begin{enumerate} \item A multivalued partial function is polynomial-time computable with $k$ adaptive queries to NPMV if and only if it is polynomial-time computable via $2^k-1$ nonadaptive queries to NPMV. \item A characteristic function is polynomial-time computable with $k$ adaptive queries to NPMV if and only if it is polynomial-time computable with $k$ adaptive queries to NP. \item Unless the Boolean hierarchy collapses, for every $k$, $k$ adaptive (nonadaptive) queries to NPMV is different than $k+1$ adaptive (nonadaptive) queries to NPMV. \end{enumerate} Nondeterministic reducibilities, lowness and the difference hierarchy over NPMV are also studied. The difference hierarchy for partial functions does not collapse unless the Boolean hierarchy collapses, but, surprisingly, the levels of the difference and bounded query hierarchies do not interleave (as is the case for sets) unless the polynomial hierarchy collapses. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-09.ps %A Chakravarty, Sreejit %A Gong, Yiming %T A Diagnostic Simulation Algorithm for Stuck-at Faults in Combinational Circuits %R 93-09 %D March 1993 %I Department of Computer Science, SUNY Buffalo %X Two faults are said to be equivalent, w.r.t a test set $T$, iff they cannot be distinguished by any test in $T$. The sizes of the equivalence classes are used as a basis for comparing the diagnostic capability of two given test sets. A novel algorithm for computing the Equivalence Classes of stuck-at faults, in combinational(full scan) circuits, w.r.t a given test set is presented. Experimental results presented show the algorithm to be more time and space efficient than a previously known algorithm. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-10.ps %A Hexmoor, H. %A Lammens, J. %A Shapiro, S. C. %T Embodiment in GLAIR: A Grounded Layered Architecture with Integrated Reasoning for Autonomous Agents %R 93-10 %D February 1993 %I Department of Computer Science, SUNY Buffalo %X In order to function robustly in the world, autonomous agents need to assimilate concepts for physical entities and relations, grounded in perception and action. They also need to assimilate concepts for perceptual properties like color, shape, and weight, and perhaps eventually even for nonphysical objects like unicorns. The process of acquiring concepts that carry meaning in terms of the agent's own physiology we call embodiment. Unlike current robotic agents, those endowed with embodied concepts will more readily understand high level instructions. As a consequence, these robots won't have to be instructed at a low level. We have developed an autonomous agent architecture that facilitates embodiment of action and perception, and accommodates embodied concepts for both physical and nonphysical objects, properties, and relations. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-13.ps %A Lammens, J. %A Hexmoor, H. %A Shapiro, S. C. %T Of Elephants and Men %R 93-13 %D April 1993 %I Department of Computer Science, SUNY Buffalo %X In his "elephant paper", Brooks criticized the ungroundedness of traditional symbol systems, and proposed physically grounded systems as an alternative, in particular the subsumption architecture. Although we are still struggling with many of the issues involved, we believe we have some contributions to make towards solving some of the open problems with physically grounded systems, particularly with respect to whether or how to integrate the old with the new. In this paper we describe an agent architecture that specifies an integration of explicit representation and reasoning mechanisms, embodied semantics through grounding symbols in perception and action, and implicit representations of special-purpose mechanisms of sensory processing, perception, and motor control. We then present components that we place in our general architecture to build agents that exhibit situated activity and learning, and finally a physical agent implementation and two simulation studies. The gist of our paper is that the Brooksian behavior generation approach goes a long way towards modeling elephant behavior, which we find very interesting, but that in order to model more deliberative behavior we may also need something else. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-15.ps %A Hexmoor, H. %A Lammens, J. %A Caicedo, G. %A Shapiro, S. C. %T Behavior Based AI, Cognitive Processes, and Emergent Behaviors in Autonomous Agents %R 93-15 %D April 1993 %I Department of Computer Science, SUNY Buffalo %X Behavior based AI has questioned the need for modeling intelligent agency using generalized cognitive modules for perception and behavior generation. Behavior based AI has demonstrated successful interactions in unpredictable environments in the mobile robot domain. This has created a gulf between "traditional" approaches to modeling intelligent agency and behavior based approaches. We present an architecture for intelligent autonomous agents which we call GLAIR (Grounded Layered Architecture with Integrated Reasoning). GLAIR is a general multi-level architecture for autonomous cognitive agents with integrated sensory and motor capabilities. GLAIR offers an "unconscious" layer for modeling tasks that exhibit a close affinity between sensing and acting, i.e., behavior based AI modules, and a "conscious" layer for modeling tasks that exhibit delays between sensing and acting. GLAIR provides learning mechanisms that allow for autonomous agents to learn emergent behaviors and add them to their repertoire of behaviors. In this paper we will describe the principles of GLAIR and some systems we have developed that demonstrate how GLAIR based agents acquire and exhibit a repertoire of behaviors at different cognitive levels. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-16.ps %A Ali, S. %A Shapiro, S. C. %T Natural Language Processing Using a Propositional Semantic Network with Structured Variables %R 93-16 %D May 7, 1993 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-18.ps %A Sivaprakasam, S. %T Performance Enhancements in SunOS NFS %R 93-18 %D May 1993 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-20.ps %A Choi, Joongmin %T Experience-Based Learning In Deductive Reasoning Systems %R 93-20 %D May 1993 %I Department of Computer Science, SUNY Buffalo %X General knowledge is widely applicable, but relatively slow to apply to any particular situation. Specific knowledge can be used rapidly where it applies, but is only narrowly applicable. We present an automatic scheme to migrate general knowledge to specific knowledge during reasoning. This scheme relies on a nested rule representation which retains the rule builder's intentions about which of the possible specializations of the rule will be most useful. If both general and specific knowledge is available and applicable, a system may be slowed down by trying to use the general knowledge as well as, or instead of, the specific knowledge. However, if general knowledge is purged from the system after migration, the system will lose the flexibility of being able to handle different situations. To retain the flexibility without paying the price in speed, a shadowing scheme is presented that prevents general knowledge from being used when specific knowledge migrated from it is available and applicable. The combination of knowledge migration and knowledge shadowing allows a deductive reasoning system to learn from and exploit previous experience. Experience is represented by the instance relationship between the general knowledge and the specific knowledge migrated from it. We also present techniques for implementing efficient rules of inference in natural deduction systems by caching and recalling the history of rule activation steps that alleviate duplicate pattern matchings and binding conflict resolutions. To reduce the complexity of manipulating rule activation steps from exponential to polynomial, methods of distributing the information about rule activation steps are developed that minimize the number of activation steps and the number of substitution compatibility tests among shared variables. An implementation of these schemes in a network-based reasoning system is discussed. Test results are shown that demonstrate the predicted benefits of these ideas. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-07.ps %A Shu, Wei %A Wu, Min-You %T Sparse Implementation of Revised Simplex Algorithms on Parallel Computers %R 93-07 %D July 01, 1993 %I Department of Computer Science, SUNY Buffalo %X Parallelizing sparse simplex algorithms is one of the most challenging problems. Because of very sparse matrices and very heavy communication, the ratio of computation to communication is extremely low. It becomes necessary to carefully select parallel algorithms, partitioning patterns, and communication optimization to achieve a speedup. Two implementations on Intel hypercubes are presented in this paper. The experimental results show that a nearly linear speedup can be obtained with the basic revised simplex algorithm. However, the basic revised simplex algorithm has many fill-ins. We also implement a revised simplex algorithm with LU decomposition. It is a very sparse algorithm, and it is very difficult to achieve a speedup with it. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-24.ps %A Regan, Kenneth W. %T Efficient Reductions from NP to Parity Using Error-Correcting Codes (preliminary version) %R 93-24 %D June 12, 1993 %I Department of Computer Science, SUNY Buffalo %X This paper proves that every language in NP is recognized by an RP[$\oplus$P] machine whose time complexity is quasilinear, apart from the time to verify witnesses. The results significantly improve the number of random bits, success probability, and running time of Valiant and Vazirani's original construction ({\em Theor. Comp. Sci.\/} 47:85--93, 1986), and beat both the $2n$ random bits and time/success tradeoff in subsequent methods based on universal hashing. Questions of further improvements are connected to open problems in the theory of error-correcting codes. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-25.ps %A Regan, Kenneth W. %T On the Difference Between Turing Machine Time Random-Access Machine Time %R 93-25 %D July 12, 1993 %I Department of Computer Science, SUNY Buffalo %K Computational complexity, theory of computation, Turing machines, random-access machines, models, simulation, finite automata %X We introduce a model of computation called the {\em Block Move\/} (BM) model. The BM extends the {\em Block Transfer\/} (BT) model of Aggarwal, Chandra, and Snir (FOCS 1987), who studied time complexity under various {\em memory access cost functions\/} ranging from $\mu_1(a) := a$ to $\mu_{\log}(a) := \ceiling{\log_2 a}$. We show that up to factors of $\log t$ in the total running time $t$, BMs under $\mu_1$ are equivalent to multitape Turing machines, and BMs under $\mu_{\log}$ are equivalent to log-cost RAMs. We also prove that for any well-behaved $\mu$ the BM classes $\dmutime[t(n)]$ form a tight deterministic time hierarchy. Whether there is any hierarchy at all when $\mu$ rather than $t$ varies is tied to long-standing open problems of determinism vs. nondeterminism. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-26.ps %A Osorio, Mauricio %A Jayaraman, Bharat %T Subset Assertions and Negation-As Failure %R 93-26 %D July 27, 1993 %I Department of Computer Science, SUNY Buffalo %K Subset Assertions, Transitive Closures, Memoization, Negation-As-Failure, Stratified Semantics, Well-Founded Semantics %X Subset assertions provide a declarative and natural means for expressing solutions to many problems involving sets. This paper is motivated by the use of subset assertions for formulating transitive closures and solving containment constraints in applications of graph traversal and program analysis. In these applications, circular containment constraints may arise, for which we propose an operational strategy based upon memoization and reexecution of function calls. We provide formal declarative and operational semantics for this class of subset assertions. One of the main technical results of this paper is a succinct translation of subset assertions into normal program clauses [L87] such that the stratified semantics of the resulting normal programs coincides with the declarative semantics of subset assertions. This translation is interesting because the operational semantics of subset assertions appears to be very different from that of normal programs---due to the setof-like capability and the need of reexecution for subset assertions, both of which are absent in normal program clauses. (However this translation is not an acceptable implementation of subset assertions due to its inefficiency.) We also discuss the connection between our proposed declarative semantics and recent approaches such as stable and well-founded semantics. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-21.ps %A Hemaspaandra, Edith %A Naik, Ashish V. %A Ogiwara, Mitsunori %A Selman, Alan L. %T P-Selective Sets, and Reducing Search to Decision vs. Self-Reducibility %R 93-21 %D July 30, 1993 %I Department of Computer Science, SUNY Buffalo %K computational, complexity, complexity classes, p-selective sets, self-reducible, search reduces to decision, proof systems, cheatable, left cuts %Y F.1.2 Modes of Computation F.1.3 Complexity Classes (see also F.2) %X We obtain several results that distinguish self-reducibility of a language $L$ with the question of whether search reduces to decision for $L$. These include: \begin{itemize} \item[(i)] If ${\rm NE} \ne {\rm E}$, then there exists a set $L$ in ${\rm NP} - {\rm P}$ such that search reduces to decision for $L$, search does {\em not} nonadaptively reduces to decision for $L$, and $L$ is {\em not} self-reducible. \item[(ii)] If ${\rm UE} \ne {\rm E}$, then there exists a language $L \in {\rm UP} - {\rm P}$ such that search nonadaptively reduces to decision for $L$, but $L$ is {\em not} self-reducible. \item[(iii)] If ${\rm UE} \cap \mbox{co-{\rm UE}} \ne {\rm E}$, then there is a disjunctive self-reducible language $L \in {\rm UP} - {\rm P}$ for which search does {\em not} nonadaptively reduce to decision. \item[(iv)] There is an oracle relative to which satisfiable assignments cannot be computed nonadaptively relative to SAT. \end{itemize} We prove that if ${\rm NE} \not\subseteq {\rm BPE}$, then there is a language $L \in {\rm NP} - {\rm BPP}$ such that $L$ is randomly self-reducible, {\em not} nonadaptively randomly self-reducible, and {\em not} self-reducible. We obtain results concerning tradeoffs in multiprover interactive proof systems, and obtain results that distinguish checkable languages from those that are nonadaptively checkable. Many of our results depend on new techniques for constructing p-selective sets. We obtain a p-selective set that is {\em not} $\leq_{tt}^{\rm P}$-equivalent to any tally language, and we show that if ${\rm P} = {\rm PP}$, then every p-selective set is $\leq_T^{\rm P}$-equivalent to a tally language. Similarly, if ${\rm P} = {\rm NP}$, then every cheatable set is $\leq_m^{\rm P}$-equivalent to a tally language. We construct a recursive p-selective tally set that is {\em not} cheatable. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-22.ps %A Sarnath, R. %T A Randomized Parallel Algorithm for dfa-minimization %R 93-22 %D August 03, 1993 %I Department of Computer Science, SUNY Buffalo %K Parallel-algorithms, Partitioning, DFA minimization %X The problem of finding the coarsest partition of a set $S$ with respect to another partition of $S$ and one or more functions on $S$ has several applications, one of which is the state minimization of finite state automata. The problem has a well known $O(n \log n)$ sequential algorithm. In this paper, we present efficient parallel randomised algorithms for the problem. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-31.ps %A Lammens, Johan M. %A Shapiro, Stuart C. %T Learning Symbolic Names for Perceived Colors %R 93-31 %D August 16, 1993 %I Department of Computer Science, SUNY Buffalo %K color perception, learning, symbol grounding, vision, knowledge representation %Y I.2.10 Vision and Scene Understanding (see also I.4.8,I.5)-Intensity, color, photometry and thresholding I.2.4 Knowledge Representation Formalisms and Methods I.2.9 Robotics-Sensors %X We are working on a computational model of color perception and color naming, which can be seen as an instance of symbol grounding in the domain of color, or as an attempt to provide an artificial intelligent agent with embodied concepts of color. We discuss two areas of the model where learning is used: learning a non-linear mapping between two color spaces, and learning a relation between color space coordinates and a set of symbolic color names. We have used a traditional error back-propagation learning algorithm for the first problem, and are considering several different learning paradigms for the second problem, ranging from traditional clustering techniques to an experimental ``space warp'' method. Using learning gives us a relatively easy way to determine a non-linear transformation of spaces in the first case, and increases the flexibility of the approach with respect to different application needs (and languages) in the second case. We discuss the learning methods used or considered and the problems encountered. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-30.ps %A Bar-Yehuda, R. %A Dabholkar, V. %A Govindarajan, K. %A Sivakumar, D. %T Randomized Local Approximations with Applications to the MAX-CLIQUE Problem %R 93-30 %D August 17, 1993 %I Department of Computer Science, SUNY Buffalo %X We present a heuristic scheme for finding a clique of maximum size or weight. Our heuristic scheme uses approximation techniques for the weighted vertex cover problem, due to R.~Bar-Yehuda and S.~Even \cite{BE85}. The approach is based on the notion of making incremental progress towards finding a clique. At each step of our algorithm, one or more {\em local optimization} techniques are attempted, and when these techniques do not make progress, we perform {\em local approximations}. In the local approximation step, the algorithm selects a heuristic from a set of heuristics, depending on the characteristics of the graph at that stage. Once a solution is constructed, we attempt to iteratively refine the solution. Randomization plays a key role at various steps of our algorithm. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-28.ps %A Hemaspaandra, Lane A. %A Naik, Ashish V. %A Ogiwara, Mitsunori %A Selman, Alan L. %T Computing Solutions Uniquely Collapses the Polynomial Hierarchy %R 93-28 %D August 17, 1993 %I Department of Computer Science, SUNY Buffalo %K computational complexity, complexity classes, NPSV, NPMV, refinements, selectivity, lowness, advice classes, nonuniform classes, polynomial hierarchy %Y F.1.2 Modes of Computation F.1.3 Complexity Classes (see also F.2) %X Is there a {\em single-valued\/} NP function that, when given a satisfiable formula as input, outputs a satisfying assignment? That is, can a nondeterministic function cull just one satisfying assignment from a possibly exponentially large collection of assignments? We show that if there is such a nondeterministic function, then the polynomial hierarchy collapses to its second level. As the existence of such a function is known to be equivalent to the statement ``every multivalued NP function has a single-valued NP refinement,'' our result provides the strongest evidence yet that multivalued NP functions cannot be refined. We prove our result via theorems of independent interest. We say that a set $A$ is NPSV-selective (NPMV-selective) if there is a 2-ary partial function in NPSV (NPMV, respectively) that decides which of its inputs (if any) is ``more likely'' to belong to $A$; this is a nondeterministic analog of the recursion-theoretic notion of the semi-recursive sets and the extant complexity-theoretic notion of P-selectivity. Our hierarchy collapse follows by combining the easy observation that every set in NP is NPMV-selective with either of the following two theorems that we prove: (1) If $A \in {\rm NP}$ is NPSV-selective, then $A \in ({\rm NP} \cap {\rm coNP})/{\rm poly}$. (2) If $A \in {\rm NP}$ is NPSV-selective, then $A$ is Low$_2$. To wit, either result implies that if every set in NP is NPSV-selective, then the polynomial hierarchy collapses to its second level, ${\rm NP}^{\rm NP}$. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-29.ps %A Hemaspaandra, Lane A. %A Hoene, Albrecht %A Naik, Ashish V. %A Ogiwara, Mitsunori %A Selman, Alan L. %A Thierauf, Thomas %A Wang, Jie %T Selectivity: Reductions, Nondeterminism, and Function Classes %R 93-29 %D August 18, 1993 %I Department of Computer Science, SUNY Buffalo %K computational complexity, complexity classes, NPSV, NPMV, refinements, selectivity, lowness, advice classes, nonuniform classes, polynomial hierarchy, NPSV-total, reductions, equivalences %Y F.1.2 Modes of Computation F.1.3 Complexity Classes (see also F.2) %X A set is P-selective if there is a polynomial-time semi-decision algorithm for the set---an algorithm that given any two strings decides which is ``more likely'' to be in the set. This paper studies two natural generalizations of P-selectivity: the NP-selective sets and the sets reducible or equivalent to P-selective sets via polynomial-time reductions. We establish a strict hierarchy among the various reductions and equivalences to P-selective sets. We show that the NP-selective sets are in $({\rm NP} \cap {\rm coNP}/{rm Poly}$ are extended low, and those in NP are Low$_2$; we also show that NP-selective sets cannot be NP-complete unless ${\rm NP} = {\rm coNP}$. By studying more general notions of nondeterministic selectivity, we conclude that all multivalued NP functions have single-valued NP refinements only if the polynomial hierarchy collapses to its second level. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-33.ps %A Regan, Kenneth W. %T Machine Models and Linear Time Complexity %R 93-33 %D August 16, 1993 %I Department of Computer Science, SUNY Buffalo %K Complexity theory, machine models, simulations, complexity classes, linear time, lower bounds %Y F.1.1 Models of Computation (see also F.4.1)-Relations among models F.1.3 Complexity Classes (see also F.2)-Relations among complexity classes F.1.3 Complexity Classes (see also F.2)-Relations among complexity measures F.4.3 Formal Languages (D.3.1)-Classes defined by resource-bounded automata %X This article first surveys known results on simulations among commonly-studied models of sequential computation, and observes that the problem of whether these models can simulate each other in linear time is essentially wide open. Then the status of research on nonlinear lower bounds for natural problems in these models is examined. The author's {\it Block Move\/} (BM) model [K. Regan, UBCS TR 92-28, submitted for publication] is described in terms of an ``editing game'' on strings, with a cost parameter $\mu$ that reflects features of real machines. Results comparing BM and TM and RAM complexity classes are given, an avenue for possible nonlinear lower bounds is sketched, and several open problems are posed. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-35.ps %A Regan, Kenneth W. %T A New Parallel Vector Model, With Exact Characterizations of NC^k %R 93-35 %D August 17, 1993 %I Department of Computer Science, SUNY Buffalo %K Computational complexity, machine models, parallel computation, vector machines, circuits %Y F. Theory of Computation F.1.1 Models of Computation (see also F.4.1)-Unbounded-action devices (e.g., cellular automata, circuits, networks of machines) F.1.2 Modes of Computation-Alternation and nondetermination F.1.3 Complexity Classes (see also F.2)-Relations among complexity classes %X This paper develops a new and natural parallel vector model, and shows that for all $k \geq 1$, the languages recognizable in $O(\log^k n)$ time and polynomial work in the model are exactly those in NC$^k$. Some improvements to other simulations in the literature of parallel models and reversal complexity are given. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-34.ps %A Naik, Ashish V. %A Regan, Kenneth W. %A Sivakumar, D. %T Quasilinear Time Complexity Theory %R 93-34 %D August 20, 1993 %I Department of Computer Science, SUNY Buffalo %K Computational complexity, complexity classes, linear time, search vs. decision, error-correcting codes %Y F. Theory of Computation F.1.3 Complexity Classes (see also F.2)-Complexity hierarchies F.1.3 Complexity Classes (see also F.2)-Relations among complexity classes %X This paper furthers the study of quasi-linear time complexity initiated by Schnorr [J. ACM 25:136--145, 1976] and Gurevich and Shelah [Proc. Logic at Botik '89, LNCS 363, pp108--118, 1989]. We show that the fundamental properties of the polynomial-time hierarchy carry over to the quasilinear-time hierarchy. Whereas all previously known versions of the Valiant-Vazirani reduction from NP to parity run in quadratic time, we give a new construction using error-correcting codes that runs in quasilinear time. We show, however, that the important equivalence between search problems and decision problems in polynomial time is unlikely to carry over: if search reduces to decision for SAT in quasi-linear time, then all of NP is contained in quasi-polynomial time. Other connections to work by Stearns and Hunt [Math. Sys. Thy. 23:209--225, 1990] on ``power indices'' of NP languages are made. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-37.ps %A Hexmoor, Henry H. %A Lammens, Johan M. %A Shapiro, Stuart C. %T An Autonomous Agent Architecture for Integrating "Unconscious" and "Conscious", Reasoned Behaviors %R 93-37 %D August 24, 1993 %I Department of Computer Science, SUNY Buffalo %K GLAIR, autonomous agents, color perception, learning behaviors %Y I.2.0 General-Cognitive simulation I.2.4 Knowledge Representation Formalisms and Methods I.2.6 Learning (see also K.3.2) I.2.9 Robotics I.2.10 Vision and Scene Understanding (see also I.4.8,I.5)-Intensity, color, photometry and thresholding %X We outline an autonomous agent architecture, GLAIR, and one of its instantiations, the Air Battle Simulation game. Our architecture models agents with ``conscious'' and ``unconscious'' behaviors. The architecture provides for grounded symbolic representations through embodied perception, and provides a mechanism for learning behaviors. We discuss how color perception fits into the architecture as a particular case of grounding and embodiment. We also discuss how the Air Battle Simulation implements an autonomous agent conforming to the architecture, and how knowledge migration and various other features of the architecture apply to it. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-36.ps %A Naik, Ashish V. %A Baveja, Alok %A Batta, Rajan %A Caulkins, Jonathan P. %T Scheduling Crackdowns on Illicit Drug Markets %R 93-36 %D August 30, 1993 %I Department of Computer Science, SUNY Buffalo %K Crackdown Scheduling, NP-completeness, Approximation Algorithms %Y F.2.2 Nonnumerical Algorithms and Problems (see also E.2-5,G.2,H.2-3)-Sequencing and scheduling F.1.1 Models of Computation (see also F.4.1)-Computability theory E.5.1 Optimization %X This paper presents an analytical approach for scheduling crackdowns on street-corner drug markets. The crackdown scheduling problem is shown to be NP-Complete. A dynamic programming formulation is presented with an exponential time optimal algorithm. We then provide efficient optimal algorithms for several special cases and approximation algorithms for the general case. These results show that the optimal strategy is to give priority to markets that take longer to bring down and which require low levels of post-crackdown maintenance. The results are then extended to incorporate dealer displacement between drug markets. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-23.ps %A Mackey, Niloufer %T Hamilton and Jacobi Meet Again: Quaternions and the Eigenvalue Problem %R 93-23 %D May 15, 1993 %I Department of Computer Science, SUNY Buffalo %X The algebra isomorphism between M4(R)and H \tensor H, where H is the algebra of quaternions, has unexpected computational payoff: it helps construct an orthogonal similarity that 2x2 block-diagonalizes a 4x4symmetric matrix. Replacing plane rotations with these more powerful 4x4 rotations leads to a quaternion-Jacobi method in which the `weight' of 4 elements (in a 2x2 block) is transferred all at once onto the diagonal. Quadratic convergence sets in sooner, and the new method requires at least one fewer sweep than plane-Jacobi methods. An analogue of the sorting angle for plane rotations is developed for these 4x4 rotations. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-39.ps %A Sher, David B. %A Wafford, Charlotte E. %A Milun, Davin %T Relating Gibbs distributions to empirically derived marginal distributions for image analysis %R 93-39 %D November 23, 1993 %I Department of Computer Science, SUNY Buffalo %K Markov random field; Gibbs distribution; ICM; simulated annealing; MAP; pseudoinverse %Y I.2.10 Vision and Scene Understanding (see also I.4.8,I.5) I.2.6 Learning (see also K.3.2)-Parameter learning %X The log marginal probability ratios of a Gibbs distribution over an 8 connected neighborhood system is a linear function of its 66 clique weights. We empirically determine log marginal probability ratios of artificial noiseless images and use the pseudoinverse method to compute the closest Gibbs distribution. We compare these Gibbs distributions to {\it ad hoc} distributions suggested in the literature and to the empirical marginals from which they are derived. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-02.ps %A Cai, Jin-Yi %A Naik, Ashish V. %A Selman, Alan L. %T On P-selective sets and Adaptive versus Nonadaptive Queries to NP %R 94-02 %D February 02, 1994 %I Department of Computer Science, SUNY Buffalo %K p-selective, NP truth-table, adaptive queries, nonadaptive queries %Y F.1.1 Models of Computation (see also F.4.1)-Computability theory F.1.2 Modes of Computation-Alternation and nondetermination F.1.3 Complexity Classes (see also F.2) F.1.3 Complexity Classes (see also F.2)-Relations among complexity classes %X We show that if there exists a p-selective set that is NP-hard under truth-table reductions, then every function that is computable in polynomial time by truth-table access to an NP oracle is computable in polynomial time by making at most $O(\log n)$ queries to an NP oracle. As a consequence, it follows that if there exists a tt-hard p-selective set for NP, then for all $k>0,~\np\subseteq DTIME[2^{n/\log^k n}]$. Reporting progress on the question of whether every function that is computable in polynomial time by truth-table access to an NP oracle is computable in polynomial time by making at most $O(\log n)$ queries to an NP oracle, we show that if there is a constant $k$ such that \[ {\rm PF}_{{\mbox{$n^k$-tt}}}^{\rm NP} \subseteq {\rm PF}^{\rm NP}[k\lceil \log n \rceil -1], \] then P = NP. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-38.ps %A Chakravarty, Sreejit %T A Study of Theoretical Issues in the Synthesis of Delay Fault Testable Circuits %R 93-38 %D October 26, 1993 %I Department of Computer Science, SUNY Buffalo %K Delay Fault Testable Circuits; Logic Optimization; Logic Synthesis; Testability Enhancing Transformations; Testability Preserving Transformations Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-40.ps %A Jayaraman, Bharat %A Osorio, Mauricio %A Moon, Kyonghee %T Partial Order Logic Programming %R 93-40 %D November 30, 1993 %I Department of Computer Science, SUNY Buffalo %K lattices, partial orders, functional programming, logic programming, sets, monotonic functions, memoization, fixed-point computation Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-01.ps %A Ali, Syed S. %T A "Natural Logic" for Natural Language Processing and Knowledge Representation %R 94-01 %D February 09, 1994 %I Department of Computer Science, SUNY Buffalo %K Natural Language Processing, Knowledge Representation, Surface Reasoning, Subsumption, ANALOG %Y I.2.0 General-Cognitive simulation I.2.3 Deduction and Theorem Proving-Deduction (e.g., natural, rule-based) I.2.4 Knowledge Representation Formalisms and Methods-Predicate logic I.2.4 Knowledge Representation Formalisms and Methods-Representation languages I.2.4 Knowledge Representation Formalisms and Methods-Semantic networks I.2.7 Natural Language Processing-Discourse I.2.7 Natural Language Processing-Language generation I.2.7 Natural Language Processing-Language parsing and understanding %X We define a knowledge representation and inference formalism that is well suited to natural language processing. In this formalism every subformula of a formula is closed. We motivate this by observing that any formal language with (potentially) open sentences is an inappropriate medium for the representation of natural language sentences. Open sentences in such languages are a consequence of the separation of variables from their quantifier and type constraints, typically in the antecedents of rules. This is inconsistent with the use of descriptions and noun phrases corresponding to variables in language. Variables in natural language are constructions that are typed and quantified as they are used. A consequence of this is that variables in natural language may be freely reused in dialog. This leads to the use of pronouns and discourse phenomena such as ellipsis involving reuse of entire subformulas. We present an augmentation to the representation of variables so that variables are not atomic terms. These ``structured'' variables are typed and quantified as they are defined and used. This leads to an extended, more ``natural'' logical language whose use and representations are consistent with the use of variables in natural language. Structured variables simplify the tasks associated with natural language processing and generation, by localizing noun phrase processing. The formalism is defined in terms of a propositional semantic network, starting from nodes and arcs connecting nodes, subsumption, matching, to inference. It allows the resolution of some representational difficulties with certain classes of natural language sentences (e.g. the so-called ``donkey'' sentences and sentences involving branching quantifiers). Reuse phenomena, such as pronominalization and ellipsis, are captured in the representation by structure-sharing. A major advantage of this structured representation of variables is that it allows a form of terminological and derived subsumption similar to surface reasoning in natural language. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-03.ps %A Chakravarty, Sreejit %A Gong, Yiming %T Voting Model Based Diagnosis of Bridging Faults in Combinational Circuits %R 94-03 %D February 15, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-42.ps %A Chakravarty, Sreejit %A Thadikaran, Paul J. %T On Iddq Measurement Based Analysis of Bridging Faults in CMOS Circuits %R 93-42 %D November 1993 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-04.ps %A Kumar, Deepak %T From Beliefs and Goals to Intentions and Actions: An Amalgamated Model of Inference and Acting %R 94-04 %D March 11, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-23.ps %A Hexmoor, Henry %A Nute, Donald %T Methods for deciding what to do next and learning %R 92-23 %D September, 1992 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-06.ps %A Chakravarty, Sreejit %A Dabholkar, Vinay %T Minimizing Power Dissipation in Scan Circuits During Test Application %R 94-06 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo %K Power dissipation, full isolated scan, full integrated scan Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-07.ps %A Hexmoor, Henry H. %T What are routines good for? %R 94-07 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo %K We show how agents with routines a) use them to guide their everyday activity, b) use them to enrich their abstract concepts about acts. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-08.ps %A Ahmad, Ishfaq %A Wu, Min-You %A Yang, Jaehyung %A Ghafoor, Arif %T A Performance Assessment of Express on the iPSC/2 and iPSC/860 Hypercube Computers %R 94-08 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-09.ps %A Hexmoor, Henry H. %T A Methodology for Developing Competent Agents Without Sensor and Actuator Profusion %R 94-09 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-12.ps %A Govindarajan, Kannan %A Jayaraman, Bharat %A Mantha, Surya %T Preference Logic Programming: Optimization as Inference %R 94-12 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-10.ps %A Dabholkar, V.P. %A Chakravarty, S. %T Minimizing Power Dissipation in Combinational Circuits During Test Application %R 94-10 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-23.ps %A Hexmoor, Henry %A Nute, Donald %T Methods for deciding what to do next and learning %R 92-23 %D September, 1992 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-15.ps %A Cai, Jin-Yi %A Chari, Suresh %T On the Impossibility of Amplifying the Independence of Random Variables %R 94-15 %D May 04, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-14.ps %A Cai, Jin-Yi %A Hirsch, Michael D. %T Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry %R 94-14 %D May 04, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-16.ps %A Cai, Jin-Yi %T Computing Jordan Normal Forms exactly for commuting matrices in polynomial time %R 94-16 %D May 11, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-17.ps %A Cai, Jin-Yi %A Lipton, Richard J. %A lcstein, Yechezkel %T The complexity of the A B C problem resolved %R 94-17 %D May 12, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-19.ps %A Green, Frederic %A Koebler, Johannes %A Regan, Kenneth W. %A Schwentick, Thomas %A Toran, Jacobo %T The Power of the Middle Bit of a #P Function %R 94-19 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-23.ps %A Regan, Kenneth W. %T Linear-Time Algorithms in Memory Hierarchies %R 94-23 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-24.ps %A Regan, Kenneth W. %T Linear Speed-Up, Information Vicinity, and Finite-State Machines %R 94-24 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-21.ps %A Naik, Ashish V. %A Regan, Kenneth W. %A Sivakumar, D. %T Quasilinear Time Complexity Theory %R 94-21 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-18.ps %A Regan, Kenneth W. %T Linear Time and Memory-Efficient Computation %R 94-18 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-20.ps %A Li, Lide %A Ogihara, Mitsunori %A Regan, Kenneth W. %T On Information From #P Functions %R 94-20 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-22.ps %A Cai, Jin-Yi %A Lipton, Richard J. %A Longpre, Luc %A Ogihara, Mitsunori %A Regan, Kenneth W. %A Sivakumar, D. %T Communication Complexity of Key Agreement on Limited Ranges %R 94-22 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-26.ps %A Lammens, Johan M. %T A Computational Model of Color Perception and Color Naming %R 94-26 %D June 24, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-29.ps %A Regan, Kenneth W. %T Index Sets and Presentations of Complexity Classes (revised version) %R 94-29 %D July 29, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-30.ps %A Jana, Devashis %A Jayaraman, Bharat %T Set Constructors, Finite Sets, and Logical Semantics %R 94-30 %D August 08, 1994 %I Department of Computer Science, SUNY Buffalo %K set constructors, finite sets, set axioms, set unification, freeness, Herbrand models. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-43.ps %A Revankar, Shriram %T Supervised Image Segmentation %R 93-43 %D May 1993 %I Department of Computer Science, SUNY Buffalo %Y J.3.0 Biology H.1.2 User/Machine I.4.6 Segmentation I.4.7 Feature Measurement Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-34.ps %A Gong, Yiming %A Chakravarty, Sreejit %T A Diagnosis Algorithm for Bridging Faults in Combinational Circuits %R 94-34 %D September 13, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-38.ps %A Cai, Jin-Yi %A Cai, Pu %A u, Yixin %T A fully polynomial time approximation scheme in scheduling deteriorating jobs %R 94-38 %D October 02, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-28.ps %A Rappaport, William J. %T Understanding Understanding: Syntactic Semantics and Computational Cognition %R 94-28 %D October 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-33.ps %A Sivalingam, Krishna Moorty %T High-Speed Communication Protocols for All-Optical Wavelength Division Multiplexed Computer Networks %R 94-33 %D October 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-27.ps %A Govindarajan, Kannan %A Jayaraman, Bharat %A Mantha, Surya %T Preference Logic Grammars %R 94-27 %D June 24, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-13.ps %A Govindarajan, Kannan %A Jayaraman, Bharat %T Intensional AlgorithmicDebugging %R 94-13 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-25.ps %A Shu, Wei %T Runtime Incremental Parallel Scheduling (RIPS) on Distributed Memory Computers %R 94-25 %D November 11, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-32.ps %A Kumar, Amruth N. %T Component Ontological Representation of Function For Candidate Discrimination in Model Based Diagnosis %R 94-32 %D November 11, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-37.ps %A Jana, Devashis %T Semantics of Subset-Logic Languages %R 94-37 %D November 11, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-39.ps %A Curtis, Ronald Sanger %T Data Structure Complexity Metrics %R 94-39 %D November 11, 1994 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-27.ps %A Miller, Russ %T The Status of Parallel Processing Education %R 93-27 %D July, 1993 (updated subsequently) %I Department of Computer Science, SUNY Buffalo %K Parallel Processing, Education Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-06.ps %A He, Xin %T Grid Embedding of Internally Triangulated Plane Graphs without Non-empty Triangles %R 95-06 %D February 02, 1995 %I Department of Computer Science, SUNY Buffalo %K planar graphs, graph drawing %X A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as non-intersecting straight line segments. In this paper, we show that, if an internally triangulated plane graph G has no non-empty triangles (a non-empty triangle is a triangle of G containing some vertices in its interior), then G can be embedded on a grid of size W x H such that W+H <= n, W <=(n+3)/2 and H <= 2(n-1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/90-23.txt %A He, Xin %T An Improved Algorithm for the Planar 3-Cut Problem %R 90-23 %D February, 1990 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/90-26.txt %A Sanath, R. %A He, X. %T Efficient Parallel Algorithms for Selection and Searching on Sorted Matrices %R 90-26 %D February, 1990 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %A Chang, C.-S. %A DeTitta, G.T. %A Hauptman, H.A. %A Miller, R. %A Thuman, P. %A Weeks, C.M. %T Using Parallel Computers to Solve the Phase Problem of X-Ray Crystallography %R 92-15 %D June 1992 %I Department of Computer Science, SUNY Buffalo %K X-Ray Crystallography, Parallel Computing %X not available, final version appears in The International Journal of Supercomputer Applications, vol 7, no. 1, pp. 25-49 Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-01.ps %A ang, Aidong %A Nodine, Marian %A Bhargava, Bharat %T Ensuring Semi-Atomicity in Heterogeneous Distributed Database Systems %R 95-01 %D February 04, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-03.ps %A Jagota, Arun K. %A Narasimhan, Giri %A Regan, Kenneth W. %T Information Capacity of Binary Weights Associative Memories %R 95-03 %D January 24, 1995 %I Department of Computer Science, SUNY Buffalo %X We study the amount of information stored in the fixed points of randominstances of two binary weights associative memory models: the Willshaw Model (WM) and the Inverted Neural Network (INN). For these models, we show divergences between the information capacity (IC) as defined by Abu-Mostafa and Jacques, and information calculated from the standard notion of storage capacity by Palm and Grossman, respectively. We prove that the WM has asymptotically optimal IC for nearly the full range of threshold values, the INN likewise for constant threshold values, and both over all degrees of sparseness of the stored vectors. This is contrasted with the result by Palm, which required stored random vectors to be logarithmically sparse to achieve good storage capacity for the WM, and with that of Grossman, which showed that the INN has poor storage capacity for random vectors. We propose Q-state versions of the WM and the INN, and show that they retain asymptotically optimal IC while guaranteeing stable storage. By contrast, we show that the Q-state INN has poor storage capacity for random vectors. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/90-13.ps %A Rapaport, William J. %T Computer Processes and Virtual Persons: Comments on Cole's "Artificial Intelligence and Personal Identity" %R 90-13 %D May 1990 %I Department of Computer Science, SUNY Buffalo %K computer processes, virtual persons, John Searle, Chinese-Room argument, artificial intelligence, cognitive science %Y I.2 ARTIFICIAL INTELLIGENCE I.2.0 General-Cognitive simulation I.2.0 General-Philosophical foundations I.2.1 Applications and Expert Systems (see also H.4,J)-Natural language interfaces I.2.4 Knowledge Representation Formalisms and Methods-Semantic networks I.2.7 Natural Language Processing I.2.7 Natural Language Processing-Language parsing and understanding %X This is a draft of the written version of comments on a paper by David Cole, presented orally at the American Philosophical Association Central Division meeting in New Orleans, 27 April 1990. Following the written comments are 2 appendices: One contains a letter to Cole updating these comments. The other is the handout from the oral presentation. In general, I am sympathetic to Cole's arguments; my comments seek to clarify and extend the issues. Specifically, I argue that, in Searle's celebrated Chinese Room Argument, Searle-in-the-room does understand Chinese, in spite of his claims to the contrary. He does this in the sense that he is executing a computer ``process'' that can be said to understand Chinese. (The argument that the process in fact does understand Chinese is made elsewhere; here, I merely assume that *if* anything understands Chinese, it is a ``process'' executed by Searle-in-the-room.) I also show, by drawing an analogy between the way that I add numbers in my head and the way that a calculator adds numbers, that Searle-in-the-room's claim that he does not understand Chinese does not contradict the fact that, by executing the Chinese-natural-language-understanding algorithm, he does understand Chinese. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-02.ps %A Regan, Kenneth W. %A Sivakumar, D. %A Cai, Jin-Yi %T Pseudorandom Generators, Measure Theory, and Natural Proofs %R 95-02 %D January 25, 1995 %I Department of Computer Science, SUNY Buffalo %X This paper proves that if strong pseudorandom number generators or one-way functions exist, then the class of languages that have polynomial-sized circuits is not small within exponential time, in terms of the resource-bounded measure theory of Lutz. More precisely, if for some e > 0 there exist nonuniformly 2^{n^e}}-hard PSRGs, as is widely believed, then the complexity class P/poly does not have measure zero in EXP. Our results establish connections between the measure theory and the "natural proofs" of Razborov and Rudich. Our work is also motivated by Lutz's hypothesis that NP does not have measure zero in EXP; obtaining our results with NP in place of P/poly would show much more far-reaching consequences from the existence of PSRGs than are currently known. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-08.ps %A Regan, Kenneth W. %A Sivakumar, D. %T Improved Resource-Bounded Borel-Cantelli and Stochasticity Theorems %R 95-08 %D February 16, 1995 %I Department of Computer Science, SUNY Buffalo %K Resource-bounded measure, Borel-Cantelli Lemma, martingales, stochasticity %X This note strengthens and simplifies Lutz's resource-bounded version of the Borel-Cantelli lemma for density systems and martingales. We observe that the technique can be used to construct martingales that are ``additively honest,'' and also martingales that are ``multiplicatively honest.'' We use this to improve the ``Weak Stochasticity Theorem'' of Lutz and Mayordomo: their result does not address the issue of how rapidly the bias away from 1/2 converges toward zero in a ``stochastic'' language, while we show that the bias must vanish exponentially. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-07.ps %A Dabholkar, Vinay %A Chakravarty, Sreejit %A Najm, Farid %A Patel, Janak %T Cyclic Stress Tests for Full Scan Circuits %R 95-07 %D February 24, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-10.ps %A Zaionc, Marek %T Lambda Representation of Operations Between Different Term Algebras %R 95-10 %D February 28, 1995 %I Department of Computer Science, SUNY Buffalo %K lambda definability %Y F.4.1 Mathematical Logic (see also F.1.1,I.2.2-3)-Lambda calculus and related systems F.4.1 Mathematical Logic (see also F.1.1,I.2.2-3)-Recursive function theory %X There is a natural isomorphism identifying second order types of the simple typed $\lambda$ calculus with free homogeneous term algebras. Let $\tau^A$ and $\tau^B$ be types representing algebras $A$ and $B$ respectively. Any closed term of the type $\tau^A \to \tau^B$ represents a computable function between algebras $A$ and $B$. The problem investigated in the paper is to find and characterize the set of all $\lambda$ definable functions between structures $A$ and $B$. The problem is presented in a more general setting. If algebras $ A_1 ,...,A_n ,B$ are represented respectively by second order types $\tau^{A_1} ,...,\tau^{A_n},\tau^B$ then $\tau^{A_1} \to (...( \tau^{A_n} \to \tau^B )...)$ is a type of functions from the product $A_1 \times ... \times A_n$ into algebra $B$. Any closed term of this type is a representation of algorithm which transforms the tuple of terms of types $\tau^{A_1} ,...,\tau^{A_n}$ respectively into a term of type $\tau^B$, which represents an object in algebra $ B$ (see [B\"{o}B85]). The problem investigated in the paper is to find an effective computational characteristic of the $\lambda$ definable functions between arbitrary free algebras and the expressiveness of such transformations. As an example we will consider $\lambda$ definability between well known free structures such as: numbers, words and trees. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-11.dvi %A Chakravarty, Sreejit %A Fuchs, Kent %A Patel, Janak %T Evaluation and Generation of IDDQ Diagnostic Tests for Bridging Faults in Combinational Circuits %R 95-11 %D February 27, 1995 %I Department of Computer Science, SUNY Buffalo %X Diagnosis is the process of identifying the fault in a faulty chip. We assume that IDDQ measurement is used during diagnosis. A novel algorithm for evaluating the effectiveness of a set of input vectors to diagnose bridging faults in combinational circuits is presented. We also present a simulation based test generator for computing IDDQ tests for diagnosing bridging faults. Experimental evaluation of the algorithms are presented. The results obtained are very encouraging. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-15.ps %A Ehrlich, Karen %A Rapaport, William J. %T A Computational Theory of Vocabulary Expansion: Project Proposal %R 95-15 %D March 21, 1995 %I Department of Computer Science, SUNY Buffalo %K artificial intelligence, computational linguistics, natural-language understanding lexical acquisition, semantics, semantic networks, machine learning %Y I.2 ARTIFICIAL INTELLIGENCE I.2.0 General-Cognitive simulation I.2.1 Applications and Expert Systems (see also H.4,J)-Natural language interfaces I.2.3 Deduction and Theorem Proving-Nonmonotonic reasoning and belief revision I.2.4 Knowledge Representation Formalisms and Methods-Semantic networks I.2.6 Learning (see also K.3.2)-Concept learning I.2.7 Natural Language Processing-Language parsing and understanding %X This project concerns the development and implementation of a computational theory of how human readers and other natural-language-understanding systems can automatically expand their vocabulary by determining the meaning of a word from context. The word might be unknown to the reader, familiar but misunderstood, or familiar but being used in a new sense. `Context' includes the prior and immediately surrounding text, grammatical information, and the reader's background knowledge, but no access to a dictionary or other external source of information (including a human). The fundamental thesis is that the meaning of such a word (1) *can* be determined from context, (2) can be *revised* and refined upon further encounters with the word, (3) ``*converges*'' to a dictionary-like definition if enough context has been provided and there have been enough exposures to the word, and (4) eventually ``*settles down*'' to a ``steady state'', which, however, is always subject to revision upon further encounters with the word. The system is being implemented in the SNePS-2.1 knowledge-representation and reasoning system, which provides a software laboratory for testing and experimenting with the theory. This research is a component of an interdisciplinary, cognitive-science project to develop a computational cognitive model of a reader of narrative text. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-14.ps %A Jayaraman, B. %A Moon, K. %T Implementation of Subset Logic Programs %R 95-14 %D March 24, 1995 %I Department of Computer Science, SUNY Buffalo %K subset and relational clauses, sets, set matching and unification, memo tables, monotonic aggregation, lazy evaluation, abstract machine, instruction set, performance analysis Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-16.ps %A Cai, Jin-Yi %A Selman, Alan L. %T Average Time Complexity Classes %R 95-16 %D March 31, 1995 %I Department of Computer Science, SUNY Buffalo %K computational complexity, average time complexity classes, hierarchy, Average-P, logarithmico-exponentia %Y F.1.3 Complexity Classes (see also F.2)-Complexity hierarchies %X We extend Levin's theory of average polynomial time to arbitrary time bounds and prove that average time complexity classes form as fine a hierarchy as do deterministic time complexity classes. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-17.ps %A Cai, Pu %A Cai, Jin-Yi %A Naik, Ashish %T Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns %R 95-17 %D April 03, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-11.ps %A Hill, Robin K. %T Issues of Semantics in a Semantic-Network representation of Belief %R 94-11 %D April 03, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-18.ps %A Gong, Yiming %A Chakravarty, Sreejit %T A Dynamic Diagnostic Test Generation System for IDDQ Measurement Based Diagnosis of Bridging Faults %R 95-18 %D April 10, 1995 %I Department of Computer Science, SUNY Buffalo %K VLSI, Testing, Diagnosis, Test Generation, IDDQ, Bridging Fault Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-20.ps %A Zaionc, Marek %T Fixpoint Technique for Counting Terms in Typed Lambda Calculus %R 95-20 %D April 14, 1995 %I Department of Computer Science, SUNY Buffalo %K typed lambda calculus, Curry - Howard isomorphism %Y F.4.1 Mathematical Logic (see also F.1.1,I.2.2-3)-Lambda calculus and related systems %X Typed lambda calculus with denumerable set of ground types is considered. The aim of the paper is to show procedure for counting closed terms in long normal forms. It is shown that there is a surprising correspondence between the number of closed terms and the fixpoint solution of the polynomial equation in some complete lattice. It is proved that counting of terms in typed lambda calculus can be reduced to the problem of finding least fixpoint for the system of polynomial equations. The algorithm for finding the least fixpoint of the system of polynomials is considered. By the well known Curry Howard isomorphism the result can be interpreted as a method for counting proofs in the implicational fragment of the propositional intuitionistic logic. The problem of number of terms was studied but never published by Ben - Yelles and Roger Hindlay. Similarly Hirokawa proved that complexity of the question whether given type ( formula ) possess an infinite number of normal terms (proofs) is polynomial space complete. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-22.ps %A Govindarajan, Kannan %A Jayaraman, Bharat %A Mantha, Surya %T Relaxation in Constraint Logic Languages %R 95-22 %D April 25, 1995 %I Department of Computer Science, SUNY Buffalo %K constraints, preferences, constraint hierarchies, logic programming, optimization, relaxation, model-theoretic and operational semantics, modal logic, soundness and completeness Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-21.ps %A Chopra, Rajiv %A Srihari, Rohini %A Ralston, Anthony %T HyperArc Consistency and Expensive Constraints %R 95-21 %D May 05, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-24.ps %A Zaionc, Marek %T Lambda definability is decidable for second order types and for regular third order types %R 95-24 %D May 08, 1995 %I Department of Computer Science, SUNY Buffalo %K lambda definability %Y F.4.1 Mathematical Logic (see also F.1.1,I.2.2-3)-Lambda calculus and related systems %X It has been proved by Loader that Statman-Plotkin conjecture fails. It means that it is undecidable to determine whether or not the given function in the full type hierarchy is lambda definable. The Loader proof was done by encoding the word problem in the full type hierarchy based on the domain with 7 elements. The aim of this paper is to show that the lambda definability problem limited for second order types and regular third order types is decidable in any finite domain. Obviously lambda definability is decidable for 0 and 1 order types. As an additional effect of the result described we may observe that for certain types there is no finite grammar generating all closed terms. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/92-16.dvi %A Chakravarty, Sreejit %A Thadikaran, Paul J. %T Generation and Simulation of IDDQ Tests for Bridging and Leakage Faults in Combinational Circuits %R 92-16 %D June 1992 %I Department of Computer Science, SUNY Buffalo %X In the absence of information about the layout and for better defect coverage test generation and fault simulation systems must target all bridging faults. The usefulness of targeting a subset of such faults, viz. all two line bridging faults, is based on the fact that an IDDQ Test Set that detects all two line bridging faults also detects all multiple line, single cluster bridging faults. A novel algorithm for simulating IDDQ Tests for all two-line bridging faults in combinational circuits is presented. The algorithm uses an implicit representation of the fault list thereby resulting in a time and space efficient algorithm. We show that the problem of computing IDDQ Tests for a two line bridging fault as well as for a leakage fault, in some restricted classes of circuits, is intractable. Next, experimental results on using randomly generated IDDQ Test Sets for detecting bridging faults are presented. These results point to the computational feasibility of targeting all two line bridging fault in combinational circuits. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-25.ps %A Koepsell, David R. %A Rapaport, William J. %T The Ontology of Cyberspace: Questions and Comments %R 95-25 %D April 22, 1995 %I Department of Computer Science, SUNY Buffalo %K ontology, cyberspace, philosophical issues, copyright, patent, legal issues %Y D.2.9 Management-Copyrights I.2.0 General-Philosophical foundations K.5 LEGAL ASPECTS OF COMPUTING K.5.1 Software Protection-Copyrights K.5.1 Software Protection-Patents K.5.1 Software Protection-Trade secrets K.5.m Miscellaneous-Hardware patents %X This document consists of two papers: "The Ontology of Cyberspace: Preliminary Questions", by David R. Koepsell, and "Comments on `The Ontology of Cyberspace'," by William J. Rapaport. They were originally presented at the Tri-State Philosophical Association Meeting, St. Bonaventure University, 22 April 1995. This document is SUNY Buffalo Department of Computer Science Technical Report 95-25 and SUNY Buffalo Center for Cognitive Science Technical Report 95-09. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/93-41.ps %A Cai, Jin-Yi %A Fuchs, W.H.J. %A Kozen, Dexter %A Liu,icheng %T Efficient Average-Case Algorithms for the Modular Group %R 93-41 %D June 15, 1995 (modified version) %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-27.ps %A Cai, Jin-Yi %A Liu,icheng %T The bounded membership problem of the monoid SL_2(N) %R 95-27 %D June 15, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-29.ps %A Babai, L. %A Beals, R. %A Cai, J-Y. %A Ivanyos, G. %A Luks, E. %T Multiplicative equations over commutative matrices %R 95-29 %D July 13, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-30.ps %A Cai, Jin-Yi %A Sivakumar, D. %T The Resolution of a Hartmanis Conjecture %R 95-30 %D July 13, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-31.ps %A Cai, Jin-Yi %A Naik, Ashish V. %A Sivakumar, D. %T On the Existence of Hard Sparse Sets under Weak Reductions %R 95-31 %D July 13, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-23.ps %A Milun, Davin %T Generating Markov Random Field Image Analysis Systems from Examples %R 95-23 %D May 1, 1995 %I Department of Computer Science, SUNY Buffalo %K MRF ; pattern recognition ; edge detection ; low level computer vision %Y I.5.2 Design Methodology I.2.6 Learning (see also K.3.2)-Parameter learning %X This thesis develops image interpretation systems from training sets of images. The system learns Markov random field parameters by sampling from this training set. Specialized MRFs can model both the image and the noise processes. The method has been tested in the domains of binary image reconstruction, edge detector enhancement and edge detection. Capturing the noise process within the MRF parameters is achieved by sampling neighborhoods in the original images together with the corresponding neighborhoods in the noisy images, and so creating a probability density function over pairs of neighborhoods across both images. This technique is that of Double Neighborhood MRF (DNMRF). This technique can even capture the noise model in situations where the noise is correlated. The task that the DNMRF method performs, and the domain in which it operates, can be changed by simply providing an appropriate set of training images. The collection of domains in which this system will work are those problems where the task to be performed is localized in nature, has a binary desired result, and has an available set of training images. The required size of the training set is studied. For standard MRFs, only 16 images of size 64x64 are required to be sampled. The performance of DNMRFs continue to improve even as the sample size increases about 256 images. The method uses optimization to interpret images. The optimizers used are the ICM gradient descent method, and simulated annealing. The sparseness of sampled MRF distributions is ameliorated by a technique developed by Hancock and Kittler. Of note are the domains of edge detection and edge detector enhancement of JPEG compressed images. In the case of edge detection the DNMRF method, when operating on binary images, performed as well as, or even better than, other well known edge detectors, such as Sobel and Canny. In the case of edge enhancement of JPEG compressed images, the method greatly improved the output of the edge detector. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-35.ps %A Niyogi, Debashish %T A Knowledge-Based Approach to Deriving Logical Structure from Document Images %R 94-35 %D August 1994 %I Department of Computer Science, SUNY Buffalo %K Document Understanding ; Image Analysis ; Artificial Intelligence ; Pattern Recognition Layout Analysis ; Digital Libraries ; Logic Programming ; Knowledge-Based Systems %X An important application of artificial intelligence is document image understanding, specifically the analysis of document images to derive a symbolic description of the document structure and contents. This requires the segmentation of the different blocks of printed matter using standard image processing techniques, and the use of spatial domain knowledge to first classify these blocks (e.g., text paragraphs, photographs, etc.), then group these blocks into logical units (e.g., newspaper stories, magazine articles, etc.), and finally determine the reading order of the text blocks within each logical unit. The above steps describe the problem of converting the physical structure of the document into its logical structure with the use of domain knowledge about document layout. The objective of this work is to develop a computational model for the derivation of the logical structure of documents using certain formalisms designed for this task. In this model, a simple yet powerful rule-based control strategy utilizes the data obtained from the invocation of different types of operations on a digitized document image, and makes inferences about the document using a knowledge base of document layout rules. The domain knowledge about document structure is represented in a unified multi-level hierarchical form, and is used by reasoning processes to make inferences. The main issues investigated in this research are: the kinds of domain and control knowledge that are required, how to represent this knowledge in a globally integrated form, and how to devise a control strategy that efficiently utilizes this knowledge. A knowledge-based document logical structure derivation system (DeLoS) has been developed based on this model. The system consists of a hierarchical rule-based control system that guides the block classification, block grouping and read-ordering operations; a global data structure that stores the document image data and incremental inferences; and a domain knowledge base that encodes the rules governing document layout. Applications of this approach include use in digital libraries for the retrieval of relevant logical document information, as well as in comprehensive document understanding systems that can read document text and allow interactive querying of the syntactic and semantic information in a document. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-12.ps %A ang, Aidong %A Cheng, Biao %A Acharya, Raj %T Texture-Based Image Retrival Using Fractals %R 95-12 %D July 21, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-35.ps %A Cai, Jin-Yi %T A simple improvement of a theorem of Polya %R 95-35 %D August 10, 1995 %I Department of Computer Science, SUNY Buffalo %K quadratic residues Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-36.ps %A Cai, Jin-Yi %T Frobenius's degree formula and Toda's polynomials %R 95-36 %D August 10, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-34.ps %A Wu, Min-You %T On Runtime Parallel Scheduling %R 95-34 %D August 10, 1995 %I Department of Computer Science, SUNY Buffalo %X Parallel scheduling is a new approach for load balancing. In parallel scheduling, all processors cooperate together to schedule work. Parallel scheduling is able to accurately balance the load by using global load information at compile-time or runtime. It provides a high-quality load balancing. This paper presents an overview of the parallel scheduling technique. Particular scheduling algorithms for tree, hypercube, and mesh networks are presented. These algorithms can fully balance the load and maximize locality at runtime. Communication costs are significantly reduced compared to other existing algorithms. Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-31.ps %A ang, Aidong %T Impact of Multimedia Data on Workflow %R 94-31 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/94-43.ps %A ang, Aidong %A Nodine, Marian %A Bhargava, Bharat %T Ensuring Semi-Atomicity in Heterogeneous Distributed Database Systems %R 94-43 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-05.ps %A ang, Aidong %A Cheng, Biao %A Acharya, Raj %T Using Fractal Coding to Index Image Content for a Digital Library %R 95-05 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-19.ps %A ang, Aidong %A Cheng, Biao %A Acharya, Raj %T Texture-Based Image Retrieval Using Fractal Codes %R 95-19 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-33.ps %A ang, Aidong %T On Synchronized Presentation Management in Multimedia Database Systems %R 95-33 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-39.ps %A Regan, K.W. %A Vollmer, H. %T Gap Languages and Log-Time Complexity Classes %R 95-39 %D September 12, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-40.ps %A Cai, Jin-Yi %A Sivakumar, D. %T Resolution of Hartmanis' Conjecture for NL-hard sparse sets %R 95-40 %D September 18, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-41.ps %A Cai, Jin-Yi %A Ogihara, Mitsunori %T Sparse Sets versus Complexity Classes %R 95-41 %D September 18, 1995 %I Department of Computer Science, SUNY Buffalo Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cs.buffalo.edu/pub/tech-reports/95-43.ps %A Ravikumar, S. %A Sivakumar, D. %T On Self-Testing without the Generator Bottleneck %R 95-43 %D September 20, 1995 %I Department of Computer Science, SUNY Buffalo %X Suppose P is a program designed to compute a linear function f on a group G. The task of "self-testing" f, that is, testing if P computes f correctly on most inputs, usually involves checking if P computes f correctly on all the generators of G. Recently, F. Ergun presented self-testers that avoid this "generator bottleneck" for specific functions. In this paper, we generalize Ergun's results, and extend them to a much larger class of functions Our results give efficient self-testers for polynomial differentiation, integration, arithmetic in large finite field extensions, and constant-degree polynomials over large rings. Thu, 21 Sep 1995 17:10:00 GMT %U http://www.cs.buffalo.edu/pub/tech-reports/95-42.ps %A Cai, Jin-Yi %A Naik, Ashish V. %A Sivakumar, D. %T Bounded Truth Table Reductions of P %R 95-42 %D Sept. 21, 1994 %I Department of Computer Science, SUNY Buffalo Fri, 22 Sep 1995 03:00:12 GMT %U http://www.cse.buffalo.edu/tech-reports/95-38.ps %A Seni, Giovanni %T Large Vocabulary Recognition of On-line Handwritten Cursive Words %R 95-38 %D August 1, 1995 %I Department of Computer Science, SUNY Buffalo %K Handwriting recognition, Pen computing, Neural network applications %X A critical feature of any computer system is its interface with the user. This has led to the development of user interface technologies such as mouse, touchscreen and pen-based input devices. Since handwriting is one of the most familiar communication media, pen-based interfaces combined with automatic handwriting recognition offers a very easy and natural input method. Pen-based interfaces are also essential in mobile computing because they are scalable. Recent advances in pen-based hardware and wireless communication have been influential factors in the renewed interest in on-line recognition systems. \\ On-line handwriting recognition is fundamentally a pattern classification task; the objective is to take an input pattern, the handwritten signal collected on-line via a digitizing device, and classify it as one of a pre-specified set of words (i.e., the system's lexicon). Because exact recognition is very difficult, a lexicon is used to constrain the recognition output to a known vocabulary. Lexicon size affects recognition performance because the larger the lexicon, the larger the number of words that can be confused. Most of the research efforts in this area have been devoted to the recognition of isolated characters, or run-on hand-printed words. A smaller number of recognition systems have been devised for cursive words, a difficult task due to the presence of the letter segmentation problem (partitioning the word into letters), and large variation at the letter level. Most existing systems restrict the working dictionary sizes to less than a few thousand words. \\ This research focused on the problem of cursive word recognition. In particular, I investigated the issues of how to efficiently deal with large lexicon sizes, the role of dynamic information over traditional feature-analysis models in the recognition process, the incorporation of letter context and avoidance of error-prone segmentation of the script by means of an integrated segmentation and recognition approach, and the use of domain information in the postprocessing stage. These ideas were used to good effect in a recognition system that I developed; this system, operating on a 21,000-word lexicon , was able to correctly recognize 88.1% (top-10) and 98.6% (top-10) of the writer-independent and writer-dependent test set words respectively. Mon, 16 Oct 1995 16:25:34 GMT %U http://www.cse.buffalo.edu/tech-reports/95-45.ps %A Slavik, Petr %T Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems %R 95-45 %D October 15, 1995 %I Department of Computer Science, SUNY Buffalo %K Approximation Algorithms, Combinatorial Optimization, Greedy Algorithm. %X We establish significantly improved bounds on the performance of the greedy algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our improvements result from a new approach to both problems. In particular, (a) we improve the known bound on the performance ratio of the greedy algorithm for general covers without cost, showing that it differs from the classical harmonic bound by a function which approaches infinity (as the size of the base set increases); (b) we show that, for covers without cost, the performance guarantee for the greedy algorithm is significantly better than the performance guarantee for the randomized rounding algorithm; (c) we prove that the classical bounds on the performance of the greedy algorithm for complete covers with costs are valid for partial covers as well, thus lowering, by more than a factor of two, the previously known estimate. Wed, 18 Oct 1995 13:48:31 GMT %U http://www.cse.buffalo.edu/tech-reports/95-46.ps %A Wu, Min-You %T Parallel Incremental Scheduling %R 95-46 %D October 24, 1995 %I Department of Computer Science, SUNY Buffalo %K Task-parallel model, load balancing, incremental scheduling, parallel scheduling %X Parallel incremental scheduling is a new approach for load balancing. In parallel scheduling, all processors cooperate together to balance the workload. Parallel scheduling accurately balances the load by using global load information. In incremental scheduling, the system scheduling activity alternates with the underlying computation work. This paper provides an overview of parallel incremental scheduling. Different categories of parallel incremental scheduling are discussed. This paper will appear in to appear in "Parallel Processing Letters." Wed, 25 Oct 1995 18:33:25 GMT %U http://www.cse.buffalo.edu/tech-reports/95-47.ps %A Wu, Min-You %T Symmetrical Hopping: a Scalable Scheduling Algorithm for Irregular Problems %R 95-47 %D October 25, 1995 %I Department of Computer Science, SUNY Buffalo %K Scheduling, distributed memory machines, irregular problems, scalability %X A runtime support is necessary for parallel computations with irregular and dynamic structures. One important component in the support system is the runtime scheduler which balances the working load in the system. We present a new algorithm, Symmetrical Hopping, for dynamic scheduling of ultra-lightweight processes. It is a dynamic, distributed, adaptive, and scalable scheduling algorithm. This algorithm is described and compared to four other algorithms that have been proposed in this context, namely the random allocation, the sender-initiated scheduling, the receiver-initiated scheduling, and the gradient model. The performance of these algorithms on Intel Touchstone Delta is presented. The experimental results show that the Symmetrical Hopping algorithm achieves much better performance due to its adaptiveness. This paper appears in "Concurrency: Practice and Experience," vol. 7, no. 7, pp. 689-706, Oct. 1995. Wed, 25 Oct 1995 18:34:09 GMT %U http://www.cse.buffalo.edu/tech-reports/95-48.ps %A Chakravarty, S. %T A Sampling Technique for Diagnostic Fault Simulation %R 95-48 %D October 26, 1995 %I Department of Computer Science, SUNY Buffalo %K Diagnostic Fault Simulation, Sampling, Approximation Algorithms %X The quality of diagnostic test sets (DTS) are determined using diagnostic fault simulation(DFS). Approximation algorithms, based on "sampling", for this computationally difficult problem are explored. "Fault Sampling", used very effectively for fault simulation, cannot be used for DFS. As an alternative we propose using "EC/IC Sampling" for DFS. It samples the set of equivalence classes(EC)/indistinguishible classes (IC). An approach to sample ECs/ICs implicitly, without explicitly enumerating the set of ECs/ICs is presented. Experimental evaluation of the proposed technique show it to be very effective. Thu, 26 Oct 1995 19:11:53 GMT %U http://www.cse.buffalo.edu/tech-reports/95-50.ps %A Govindarajan, Kannan %A Jayaraman, Bharat %A Mantha, Surya %T Preference Datalog %R 95-50 %D November 01, 1995 %I Department of Computer Science, SUNY Buffalo %K preference, datalog, optimization, relaxation, bottom-up evaluation, semantics, magic rewriting Wed, 08 Nov 1995 20:11:45 GMT %U http://www.cse.buffalo.edu/tech-reports/95-49B.ps %A Rapaport, William J. %A Shapiro, Stuart C. %A Wiebe, Janyce M. %T Quasi-Indexicals and Knowledge Reports %R 95-49B %D October 26, 1995 %I Department of Computer Science, SUNY Buffalo %K artificial intelligence, knowledge representation, computational linguistics, quasi-indexicals, belief representation %X We present a computational analysis of de re, de dicto, and de se belief and knowledge reports. Our analysis solves a problem first observed by Hector-Neri Castan}da, namely, that the simple rule `(A knows that P) implies P' apparently does not hold if P contains a quasi-indexical. We present a single rule, in the context of a knowledge-representation and reasoning system, that holds for all P, including those containing quasi-indexicals. In so doing, we explore the difference between reasoning in a public communication language and in a knowledge-representation language, we demonstrate the importance of representing proper names explicitly, and we provide support for the necessity of considering sentences in the context of extended discourse (for example, written narrative) in order to fully capture certain features of their semantics. Wed, 08 Nov 1995 20:32:01 GMT %U http://www.cse.buffalo.edu/tech-reports/95-51.ps %A Fenner, Stephen %A Green, Frederic %A Homer, Stephen %A Selman, Alan L. %A Thierauf, Thomas %A Vollmer, Heribert %T Complements of Multivalued Functions %R 95-51 %D November 06, 1995 %I Department of Computer Science, SUNY Buffalo %K conNPMV, multivalued functions, query hierarchy, difference hierarchy %X We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that, surprisingly, it is essentially the same as that of NPMV^{NP}. Complete functions for coNPMV are exhibited and central complexity-theoretic properties of this class are studied. We show that computing maximum satisfying assignments can be done in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes MaxP and MinP. The difference hierarchy for NPMV is related to the query hierarchy for coNPMV. Finally, we examine a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse of the polynomial time hierarchy. Wed, 08 Nov 1995 20:33:40 GMT %U http://www.cse.buffalo.edu/tech-reports/95-49A.ps %A Wu, Min-You %T On Parallelization of Static Scheduling Algorithms %R 95-49A %D October 31, 1995 %I Department of Computer Science, SUNY Buffalo %K Static scheduling, parallelization, scheduling quality, complexity, speedup %X Most static scheduling algorithms that schedule parallel programs represented by directed acyclic graphs (DAGs) are sequential. This paper discusses the essential issues of parallelization of static scheduling and presents two efficient parallel scheduling algorithms. The proposed algorithms have been implemented on an Intel Paragon machine, and their performance has been evaluated. These algorithms produce high-quality scheduling and are much faster than existing sequential and parallel algorithms. Wed, 08 Nov 1995 20:36:17 GMT %U http://www.cse.buffalo.edu/tech-reports/95-37.ps %A Govindarajan, Kannan %A Jayaraman, Bharat %A Mantha, Surya %T Optimization and Relaxation in Constraint Logic Languages %R 95-37 %D October 21, 1995 %I Department of Computer Science, SUNY Buffalo %K constraints, logic programming, optimization, relaxation, preference, formal semantics, modal logic Wed, 08 Nov 1995 20:50:14 GMT %U http://www.cse.buffalo.edu/tech-reports/95-52.ps %A Dabholkar, Vinay P. %A Chakravarty, Sreejit %T Stress Tests for Dynamic Burn-in of Full Scan Circuits %R 95-52 %D November 09, 1995 %I Department of Computer Science, SUNY Buffalo %X Dynamic burn-in is an important process that is used to improve the reliability of circuits. In this paper, we investigate the problem of computing cyclic sequences which can be used during burn-in of full scan circuits. We show that the problems are computationally difficult. In addition, we demonstrate experimentally that good heuristics can be developed to compute stress test for dynamic burn-in of full scan circuits. Thu, 09 Nov 1995 20:37:09 GMT %U http://www.cse.buffalo.edu/tech-reports/95-44.ps %A ang, Aidong %A Gollapudi, Sreenivas %T Multimedia Transaction Management in Database Systems %R 95-44 %D October 30, 1995 %I Department of Computer Science, SUNY Buffalo %X Current database management system techniques are insufficient to support the management of multimedia data owing to their time-sampled nature. The extension of database systems to support multimedia applications thus requires new mechanisms to ensure the synchronized presentation of multimedia data streams. In order to flexibly and efficiently present multimedia data streams to users, media streams must be segmented into media objects with time constraints among these objects specified and maintained. In this paper, we investigate a framework and systematic strategies for supporting the continuous and synchronized retrieval and presentation of multimedia data streams in a multimedia database system. Specifically, we will develop: (1) a practical framework for specifying multimedia transactions and schedules and the appropriate synchronization constraints between different media streams; (2) multimedia transaction scheduling principles underlying the synchronized presentation of multimedia data streams when delay effects are considered; and (3) pragmatic techniques for multimedia transaction scheduling to support the synchronized presentation of multimedia data streams in object-oriented database systems. Wed, 15 Nov 1995 19:48:46 GMT %U http://www.cse.buffalo.edu/tech-reports/95-54.ps %A Slavik, Petr %T A Tight Analysis of the Greedy Algorithm for Set Cover %R 95-54 %D November 19, 1995 %I Department of Computer Science, SUNY Buffalo %K Approximation Algorithms, Combinatorial Optimization, Fractional Set Cover, Greedy Algorithm, Partial Set Cover, Set Cover. %X We establish significantly improved bounds on the performance of the greedy algorithm for approximating set cover. In particular, we provide the first substantial improvement of the 20 year old classical harmonic upper bound, H(m), of Johnson, Lovasz, and Chvatal, by showing that the performance ratio of the greedy algorithm is, in fact, exactly ln m - ln ln m + Theta(1), where m is the size of the ground set. The difference between the upper and lower bounds turns out to be less than 1.1. This provides the first tight analysis of the greedy algorithm, as well as the first upper bound that lies below H(m) by a function going to infinity with m. We also show that the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on the integrality gap. Our improvements result from a new approach which might be generally useful for attacking other similar problems. Tue, 21 Nov 1995 16:41:51 GMT %U http://www.cse.buffalo.edu/tech-reports/95-55.ps %A Gollapudi, Sreenivas %A ang, Aidong %T Buffer Management in Multimedia Database Systems %R 95-55 %D November 28, 1995 %I Department of Computer Science, SUNY Buffalo %X The delivery of continuous and synchronous multimedia data from a database server to multiple destinations over a network presents new challenges in the area of buffer management. Many factors that were not considered in conventional buffer management must be examined. In this paper, we investigate the principles of buffer management for multimedia data presentations in object-oriented database environments. The primary goal is to minimize the response time of multimedia presentations while ensuring that all continuity and synchronization requirements are satisfied. Minimum buffering requirements to guarantee the continuity and synchrony ofi the presentation of multimedia data are first proposed. A prefetching technique which satisfies these requirements is then developed. These principles and technique provide users with the full range of information required to develop a database environment for multimedia presentations. Tue, 28 Nov 1995 21:23:37 GMT %U http://www.cse.buffalo.edu/tech-reports/96-02.ps %A Kumar, Ravi S. %A Sivakumar, D. %T Efficient Self-Testing of Linear Recurrences %R 96-02 %D January 29, 1996 %I Department of Computer Science, SUNY Buffalo %K self-testing, recurrences, polynomials %X We consider the problem of designing efficient self-testers for linear recurrences, and present a complete package of self-testers for this class of functions. The results are proved by demonstrating an efficient reduction from this problem to the problem of testing linear functions over certain matrix groups. Our tools include spectral analysis of matrices over finite fields, and various counting arguments that extend known techniques. The matrix twist yields completely new self-testers for polynomials over the finite field/p. The efficiency of our polynomial self-testers is better than all previously known testers, and in the univariate case, we are able to match the efficiency of the Blum-Luby-Rubinfeld linearity tester. We also present self-testers for convolution identities over groups, and improved self-testers for polynomials over rational domains. Mon, 19 Feb 1996 16:39:52 GMT %U http://www.cse.buffalo.edu/tech-reports/96-03.ps %A Chakravarty, Sreejit %A Thadikaran, Paul J. %T Which Set of Bridging Faults Should Test Compilers Target? %R 96-03 %D February 28, 1996 %I Department of Computer Science, SUNY Buffalo %K Bridging Faults, Fault Simulation, IDDQ Testing, Test Compilation, Test Compression,Test Generation %Y B.1.3; B.2.3; B.3.4; B.5.3; B.6.2; B.6.3; B.7.2 %X Existing test compilers target stuck-at faults. Recent experimental evidence suggest targetting bridging faults(BFs) because they model between 40-50% of physical defects. For BFs, one suggestion has been to extract a small set of BFs using "layout analysis". We argue that this is not a feasible option for test compilers thereby making a case for "layout independent analysis" of BFs. Opting for "layout independent analysis" implies that computer-aided test tools target "all possible BFs". Targetting such a large number of faults is generally considered unreasonable. We present new experimental data and analyze published data. The analysis reveal that for many problems very good techniques have already been developed to target such a large number of faults. Mon, 04 Mar 1996 19:10:46 GMT %U http://www.cse.buffalo.edu/tech-reports/96-01.ps %A Ivanyos, Gįbor %T Testing membership in unitriangular matrix groups. Preliminary draft %R 96-01 %D January 02, 1996 %I Department of Computer Science, SUNY Buffalo %X We present an algorithm that, given a subgroup G of the group of the upper triangular matrices with rational entries by a set of generators, computes generators of the lower central series of G. As an application, we show that the constructive membership problem in G can be performed in polynomial time. This draft is intended to be part of a larger project investigating the complexity of computational problems in finitely generated linear groups. Mon, 04 Mar 1996 19:30:57 GMT %U http://www.cse.buffalo.edu/tech-reports/96-05.ps %A Hong, Tao %T Degraded Text Recognition using Visual and Linguistic Context %R 96-05 %D March 27, 1996 %I Department of Computer Science, SUNY Buffalo %K OCR, Document Recognition, Contextual Analysis %Y I.5 PATTERN RECOGNITION %X To improve the performance of an OCR system on degraded images of text, postprocessing techniques are critical. The objective of postprocessing is to correct errors or to resolve ambiguities in OCR results by using contextual information. Depending on the extent of context used, there are different levels of postprocessing. In current commercial OCR systems, word-level postprocessing methods, such as dictionary-lookup, have been applied successfully. However, many OCR errors cannot be corrected by word-level postprocessing. To overcome this limitation, passage-level postprocessing, in which global contextual information is utilized, is necessary. This thesis addresses problems in degraded text recognition and discusses potential solutions through passage-level postprocessing. The objective is to develop a postprocessing methodology from a broader perspective. In this work, two classes of inter-word contextual constraints, visual constraints and linguistic constraints, are exploited extensively. Given a text page with hundreds of words, many word image instances can be found visually similar. Formally, six types of visual inter-word relations are defined. Relations at the image level must be consistent with the relations at the symbolic level if word images in the text have been interpreted correctly. Based on the fact that OCR results often violate this consistency, methods of visual consistency analysis are designed to detect and correct OCR errors. Linguistic knowledge sources such as lexicography, syntax, and semantics, can be used to detect and correct OCR errors. Here, we focus on the word candidate selection problem. In this approach an OCR provides several alternatives for each word and the objective of postprocessing is to choose the correct decision among these choices. Two approaches of linguistic analysis, statistical and structural, are proposed for the problem of candidate selection. A word-collocation-based relaxation algorithm and a probabilistic lattice parsing algorithm are proposed. There exist some OCR errors which are not easily recoverable by either visual consistency analysis or linguistic consistency analysis. Integration of image analysis and language-level analysis provides a natural way to handle difficult words. Wed, 27 Mar 1996 14:20:00 GMT %U http://www.cse.buffalo.edu/tech-reports/96-06.ps %A Gollapudi, Sreenivas %A ang, Aidong %T NetMedia: A Client-Server Distributed Multimedia Database Environment %R 96-06 %D April 04, 1996 %I Department of Computer Science, SUNY Buffalo %X Advances in multimedia computing technologies offer new approaches to support on-line accesses to information from a variety of sources such as video clips, audio, images, and books. A client-server distributed multimedia system would be a practical approach to support such functionalities. In this paper, we present the design and implementation of a client-server distributed multimedia database environment that can be used to support large digital libraries. System architecture and design are described. Server functionalities, including client scheduling, data buffering and admission control, are investigated. A client request can only be admitted if both the quality-of-service (QoS) requirements from the client and the upper bound on total buffer consumption at the server are maintained. Tue, 09 Apr 1996 19:59:15 GMT %U http://www.cse.buffalo.edu/tech-reports/96-08.ps %A Dabholkar, Vinay P. %A Chakravarty, Sreejit %T Dynamic Stress Tests for ``Narrow Metal Imperfections'' in Full Scan Circuits %R 96-08 %D April 03, 1996 %I Department of Computer Science, SUNY Buffalo %K Stress tests, Dynamic burn-in %X Dynamic stress testing is an important process that is used to improve the reliability of circuits. In this paper, we investigate the problem of computing cyclic sequences which can be used during burn-in of full scan circuits. Using a switching activity model we show that the stress due to electromigration and hot-electron degradation can be accurately modeled. Notwithstanding the difficulty of computing optimal dynamic stress tests, we demonstrate experimentally that efficient heuristics can be developed to compute good dynamic stress tests for full scan circuits. Tue, 09 Apr 1996 20:00:59 GMT %U http://www.cse.buffalo.edu/tech-reports/96-09.ps %A Min-You Wu %T Scheduling for Large-Scale Parallel Video Servers %R 96-09 %D May 17, 1996 %I Department of Computer Science, SUNY Buffalo %K Video servers, parallel systems, scheduling, load-balancing, admission control %X Parallel video servers are necessary for large-scale video-on-demand and other multimedia systems. This paper addresses the scheduling problem of parallel video servers. We discuss scheduling requirements. Optimal algorithms are presented for conflict-free scheduling, delay minimization, load balancing, and admission control. Fri, 17 May 1996 18:10:35 GMT %U http://www.cse.buffalo.edu/tech-reports/96-10.ps %A Rapaport, William J. %T How Minds Can Be Computational Systems %R 96-10 %D May 31, 1996 %I Department of Computer Science, SUNY Buffalo %K computationalism, cognitive science, algorthims, heuristics, semiotics %Y I.2.0;I.2.4 %X The proper treatment of computationalism, as the thesis that cognition is computable, is presented and defended. Some arguments of James H. Fetzer against computationalism are examined and found wanting, and his positive theory of minds as semiotic systems is shown to be consistent with computationalism. An objection is raised to an argument of Selmer Bringsjord against one strand of computationalism, viz., that Turing-Test-passing artifacts are persons; it is argued that, whether or not this objection holds, such artifacts will inevitably be persons. Fri, 31 May 1996 15:34:45 GMT %A Hexmoor, Henry %A Meeden, Lisa %T Robolearn 96: An International Workshop on Learning for Autonomous Robots %R 96-11 %D June 10, 1996 %I Department of Computer Science, SUNY Buffalo %K Robots, Machine Learning, Agent Architecture %Y Computer Science; Robotics %X Proceedings of a workshop held in Key West, Florida, USA. May 19-20, 1996. Mon, 10 Jun 1996 20:13:25 GMT %U http://www.cse.buffalo.edu/tech-reports/96-12.ps %A Boxer, Laurence %A Miller, Russ %A Rau-Chaplin, Andrew %T Some Scalable Parallel Algorithms for Geometric Problems %R 96-12 %D June 14, 1996 %I Department of Computer Science, SUNY Buffalo %K parallel algorithms, computational geometry, scalable algorithms, coarse grained multicomputer, lower envelope %Y G.1.0;I.3.5;C.1.2 %X This paper considers a variety of geometric problems on input sets of size n using a coarse grained multicomputer model consisting of p processors with $\Omega(\frac{n}{p})$ local memory each, where the processors are connected to an arbitrary interconnection network. It introduces efficient scalable parallel algorithms for a number of geometric problems including the rectangle finding problem, the iso-oriented line intersection counting problem, a variety of lower envelope problems, the minimal circle-covering problem, the maximal equally-spaced collinear points problem, and the point set pattern matching problem. All of the algorithms presented are scalable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addition to the practicality imparted by scalability, these algorithms are easy to implement in that all required communications can be achieved by a small number of calls to standard global routing operations. Fri, 14 Jun 1996 21:01:09 GMT %U http://www.cse.buffalo.edu/tech-reports/96-13.ps %A Gollapudi, Sreenivas %T A Multithreaded Client-Server Architecture for Distributed Multimedia Systems %R 96-13 %D July 19, 1996 %I Department of Computer Science, SUNY Buffalo %K Synchronization, Distributed Systems, Buffer Management %X Advances in multimedia computing technologies offer new approaches to support on-line accesses to information from a variety of sources such as video clips, audio, images, and books. A client-server distributed multimedia system would be a practical approach to support such functionalities. In this thesis, we present the design and implementation of a client-server distributed multimedia database environment that can be used to support multimedia systems such as large digital libraries. We focus on the problems of playout management and buffer management at the client and buffer management and admission control at the server. Current database management system techniques are insufficient to support the management of multimedia data owing to their time-sampled nature. The extension of database systems to support multimedia applications thus requires new mechanisms to ensure the synchronized presentation of multimedia data streams. In order to flexibly and efficiently present multimedia data streams to users, media streams must be segmented into media objects with time constraints among these objects specified and maintained. We investigate a framework and systematic strategies for supporting the continuous and synchronized retrieval and presentation of multimedia data streams at the client. The delivery of continuous and synchronous multimedia data from a database server to multiple destinations over a network presents new challenges in the area of buffer management. We investigate the principles of buffer management for multimedia data presentations in object-oriented database environments. The primary goal is to minimize the response time of multimedia presentations while ensuring that all continuity and synchronization requirements are satisfied. Minimum buffering requirements to guarantee the continuity and synchrony of the presentation of multimedia data are first proposed. A prefetching technique which satisfies these requirements is then developed. Server functionalities, including client scheduling, data buffering and admission control, are investigated. A client request can only be admitted if both the quality-of-service (QoS) requirements from the client and the upper bound on total buffer consumption at the server are maintained. Fri, 19 Jul 1996 18:30:09 GMT %U http://www.cse.buffalo.edu/tech-reports/96-14.ps %A Wu, Min-You %A Shu, Wei %T DDE: A Modified Dimension Exchange Method for Load Balancing in k-ary n-cubes %R 96-14 %D March 25, 1996 %I Department of Computer Science, SUNY Buffalo %K load balancing, parallel scheduling, direct method, k-ary n-cubes, dimension exchange %X The dimension exchange method (DEM) was initially proposed as a load-balancing algorithm for the hypercube structure. It has been generalized to k-ary n-cubes. However, the k-ary n-cube algorithm must take many iterations to converge to a balanced state. In this paper, we propose a direct method to modify DEM. The new algorithm, Direct Dimension Exchange (DDE) method, takes load average in every dimension to eliminate unnecessary load exchange. It balances the load directly without iteratively exchanging the load. It is able to balance the load more accurately and much faster. Sun, 21 Jul 1996 18:50:03 GMT %U http://www.cse.buffalo.edu/tech-reports/96-18.ps %A Chalupsky, Hans %T SIMBA: Belief Ascription by Way of Simulative Reasoning %R 96-18 %D January 31, 1996 %I Department of Computer Science, SUNY Buffalo %K belief reasoning, agent incompleteness, cognitive modeling, nonmonotonic reasoning %Y Nonmonotonic reasoning and belief revision; cognitive simulation %X A key cognitive faculty that enables humans to communicate with each other is their ability to incrementally construct and use models describing the mental states of others, in particular, models about their beliefs. Not only do humans have beliefs about the beliefs of others, they can also reason with these beliefs even if they do not hold them themselves. If we want to build an artificial or computational cognitive agent that is similarly capable, we need a formalism that is fully adequate to represent the beliefs of other agents, and that also specifies how to reason with them. Standard formalizations of knowledge or belief, in particular, the various epistemic and doxastic logics, seem to be not very well suited to serve as the formal device upon which to build an actual computational agent. They either neglect representation problems, or the reasoning aspect, or the defeasibility that is inherent in the reasoning about somebody else's beliefs, or they use idealizations which are problematic when confronted with realistic agents. Our main result is the development of SIMBA, an actually implemented belief reasoning engine that uses simulative reasoning to reason with and about the beliefs of other agents. SIMBA is built upon SL, a fully intensional, subjective logic of belief which is representationally and inferentially adequate to serve as one of the main building blocks of an artificial cognitive agent. SL can handle agents that do not believe the consequential closure of their base beliefs, or even agents which have inconsistent beliefs, differently put, it can handle the beliefs of realistic agents. It is also adequate to model introspection, it facilitates belief revision, and it has a more intuitive semantics than standard formalizations of belief. Fri, 18 Oct 1996 13:41:22 GMT %U http://www.cse.buffalo.edu/tech-reports/96-19.ps %A Rapaport, William J. %T Cognitive Science %R 96-19 %D October 29, 1996 %I Department of Computer Science, SUNY Buffalo %K cognitive science, artificial intelligence %Y I.2.0 %X This is a draft of the long version of an article to appear in Anthony Ralston, Edwin D. Reilly, and David Hemmindinger (eds.), _Encyclopedia of Computer Science, 4th edition_ (New York: Van Nostrand Reinhold, 1998). It is a revised and updated version of Rapaport, William J. (1993), ``Cognitive Science'', in Anthony Ralston & Edwin D. Reilly (eds.), _Encyclopedia of Computer Science, 3rd edition_ (New York: Van Nostrand Reinhold): 185-189, which is an abridged version of Rapaport, William J. (1990), ``Cognitive Science'', _Technical Report 90-12_ (Buffalo: SUNY Buffalo Department of Computer Science). Comments on this draft are eagerly solicited. This document is _Technical Report 96-19_ (Buffalo: SUNY Buffalo Department of Computer Science) and _Technical Report 96-4_ (Buffalo: SUNY Buffalo Center for Cognitive Science). Tue, 29 Oct 1996 19:15:50 GMT %U http://www.cse.buffalo.edu/tech-reports/96-21.ps %A Belanger, Jay %A Pavan, A. %A Wang, Jie %T Reductions Do Not Preserve Fast Convergence Rates in Average Time %R 96-21 %D November 07, 1996 %I Department of Computer Science, SUNY Buffalo %X Cai and Selman proposed a general definition of average computation time that, when applied to polynomials, results in a modification of Levin's notion of average-polynomial-time. The effect of the modification is to control the rate of convergence of the expressions that define average computation time. With this modification, they proved a hierarchy theorem for average-time complexity that is as tight as the Hartmanis-Stearns hierarchy theorem for worst-case deterministic time. They also proved that under a fairly reasonable condition on distributions, called condition W, a distributional problem is solvable in average-polynomial-time under the modification exactly when it is solvable in average-polynomial-time under Levin's definition. Various notions of reductions, as defined by Levin and others, play a central role in the study of average-case complexity. However, the class of distributional problems that are solvable in average-polynomial-time under the modification is not closed under the standard reductions. In particular, we prove that there is a distributional problem that is not solvable in average-polynomial-time under the modification but is reducible, by the identity function, to a distributional problem that is, and whose distribution even satisfies condition W. Thu, 07 Nov 1996 20:15:52 GMT %U http://www.cse.buffalo.edu/tech-reports/96-22.ps %A Cai, Jin-Yi %A Samuthiram, Karthikeyan %T A note on the Pumping Lemma for regular languages %R 96-22 %D December 04, 1996 %I Department of Computer Science, SUNY Buffalo %K pumping lemma, regular language, Myhill Nerode theorem %X We discuss the non-sufficiency of pumping lemma for regularity of languages. Thu, 12 Dec 1996 19:32:50 GMT %U http://www.cse.buffalo.edu/tech-reports/96-23.ps %A Wu, Min-You %T Scheduling for Interactive Operations in Parallel Video Servers %R 96-23 %D December 12, 1996 %I Department of Computer Science, SUNY Buffalo %K parallel video servers, real-time scheduling, interactive operations, fast forward, Quality-of-Service. %X Providing efficient support for interactive operations such as fast-forward and fast-backward is essential in video-on-demand and other multimedia server systems. In this paper, we present two basic approaches for scheduling interactive operations, the prefetching approach and the grouping approach. Scheduling algorithms are presented for both fine-grain and coarse-grain data blocks. These algorithms can precisely schedule video streams for both normal playout and interactive operations. Thu, 12 Dec 1996 19:35:58 GMT %U http://www.cse.buffalo.edu/tech-reports/96-20.ps %A Chakravarty, Sreejit %T Defect Detection Capability of Delay Tests for Path Delay Faults %R 96-20 %D November 07, 1996 %I Department of Computer Science, SUNY Buffalo %Y B.1.3 %X Defects cause faulty static logic behaviour, faulty dynamic logic behaviour and elevated IDDQ level. Recent empirical and simulation studies show that adding atspeed tests to test suites detects defective ICs missed by slow speed and IDDQ tests. Delay tests for path delay faults and transition tests are two classes of tests that are often used for isolating ICs with faulty dynamic logic behaviour. We show that both these classes of tests often fail to detect many defects that causes faulty dynamic logic behaviour. This implies that computing at speed tests is fundamentally different from computing delay tests for parametric testing and new techniques need to be developed. Thu, 12 Dec 1996 19:39:20 GMT %U http://www.cse.buffalo.edu/tech-reports/96-24.ps %A Chang, W. %A Murthy, D. %A Mei, Y. %A ang, A. %T Metadatabase and Search Agent for Multimedia Database Access over Internet %R 96-24 %D December 16, 1996 %I Department of Computer Science, SUNY Buffalo %K Various multimedia repositories are now distributed throughout the Internet and can be accessed via the World Wide Web tools. In such an environment, a challenging problem is to find the multimedia databases at distributed locations that are the most relevant to the user query. In this paper, we investigate approaches to the creation of a metadatabase and design of a search agent in a metaserver which supports the integrated access to various multimedia databases. The creation of the metadatabase formulates the metadata on the types of media data each multimedia database at a remote site houses and its query capabilities. The design of the search agent at metaserver accesses the metadatabase and control the distribution of user queries to relevant database sites through the site server. The search agent also directs interactive dialogue between the client and multimedia databases. The proposed metadatabase and search agent is deMetadata, WWW, resource discovery %X Various multimedia repositories are now distributed throughout the Internet and can be accessed via the World Wide Web tools. In such an environment, a challenging problem is to find the multimedia databases at distributed locations that are the most relevant to the user query. In this paper, we investigate approaches to the creation of a metadatabase and design of a search agent in a metaserver which supports the integrated access to various multimedia databases. The creation of the metadatabase formulates the metadata on the types of media data each multimedia database at a remote site houses and its query capabilities. The design of the search agent at metaserver accesses the metadatabase and control the distribution of user queries to relevant database sites through the site server. The search agent also directs interactive dialogue between the client and multimedia databases. The proposed metadatabase and search agent is designed and implemented in a web-based multimedia information retrieval environment. Tue, 31 Dec 1996 22:18:27 GMT %U http://www.cse.buffalo.edu/tech-reports/96-25.ps %A Johnson, T. %A ang, A. %T A Framework for Supporting Quality-Based Presentation of Continuous Multimedia Streams %R 96-25 %D December 16, 1996 %I Department of Computer Science, SUNY Buffalo %K Multimedia, presentation, %X In this paper, we investigate a framework for supporting the continuous and synchronized presentation of multimedia streams in a distributed multimedia system. Assuming that the network transmission and the server provide sufficient support for delivering media objects, important issues regarding the enforcement of smooth presentations of multimedia streams must be addressed at client sites. We develop various presentation scheduling algorithms that are adaptable to quality-of-service parameters. The significance of the proposed algorithms is to adjust the presentation from its insynchrony by gradually catching up or slowing down rather than using skipping/pausing in an abrupt fashion. Experimental analysis conducted for the proposed approaches demonstrates that our algorithms can avoid hiccups in presentations. This framework can be readily used to facilitate various applications, including education and training. Tue, 31 Dec 1996 22:18:31 GMT %U http://www.cse.buffalo.edu/tech-reports/97-01.ps %A Pavan, A. %A Selman, Alan L. %T Complete Distributional Problems, Hard Languages, and Resource-Bounded Measure %R 97-01 %D February 06, 1997 %I Department of Computer Science, SUNY Buffalo %K average time complexity, resource-bounded measure, complete distributional problems, bi-immune %X Cai and Selman \cite{CaiSelman96} defined a modification and extension of Levin's notion of average polynomial time to arbitrary time-bounds and proved that if $L$ is P-bi-immune, then for every polynomial-time computable distribution $\mu$, the distributional problem $(L, \mu)$ is not polynomial on the $\mu$-average. We prove the following consequences of the hypothesis that the $p$-measure of NP is not 0: 1. There is a language $L$ that is not P-bi-immune and for every polynomial-time computable distribution $\mu$, the distributional problem $(L, \mu)$ is not polynomial on the $\mu$-average. 2. For every DistNP-complete distributional problem $(L, \mu)$, there exists a constant $s \geq 0$ such that $\mu( \{ x ~|~ |x| \geq n \} ) = \Omega(\frac{1}{n^s})$. That is, every DistNP-complete problem has a reasonable distribution. Thu, 06 Feb 1997 16:28:15 GMT %U http://www.cse.buffalo.edu/tech-reports/97-02.ps %A Slavik, Petr %T The Errand Scheduling Problem %R 97-02 %D March 14, 1997 %I Department of Computer Science, SUNY Buffalo %K Approximation Algorithms, Combinatorial Optimization, Errand Scheduling, Generalized Steiner Tree, Generalized Traveling Salesman, LP Relaxation, Set Cover, Traveling Salesman, Tree Stripping %Y G.2.2; F.2.2; %X We consider the following natural errand scheduling problem (ESP). We must perform a set of errands at the nodes of an edge-weighted graph, and each errand can only be performed at a subset of the nodes. What is the shortest tour that allows us to complete all the errands? We also consider the closely related tree cover problem (TCP), in which we seek a tree of minimum length that ``covers'' all errands. Both problems generalize a number of well-known problems in combinatorial optimization and have a wide range of applications including job scheduling on multi-state CNC machines and VLSI design. We focus on the case in which the graph is a weighted tree; this trivially generalizes the famous set cover problem. Under the assumption that no errand can be performed in ``too many'' nodes, we obtain an algorithm that asymptotically matches the best possible approximation ratio for set cover and approximates both errand scheduling and tree cover within O(log m), where m is the total number of errands. Our algorithm is based on ``tree stripping''--a technique specifically designed to round the solution to the LP relaxation of tree cover, but is hopefully useful for approximating other related problems. In the second part of the paper, we discuss the errand scheduling and tree cover problems on a general weighted graph with the restriction that each errand can be performed at at most r nodes. We show that in this case, ESP can be approximated to within 3r/2 and TCP to within r. Wed, 26 Mar 1997 21:09:39 GMT %A Hexmoor, Henry %T ROBOLEARN 97: An International Workshop on Evaluating Robot Learning %R 97-03 %D April 12, 1997 %I Department of Computer Science, SUNY Buffalo %K Machine learning, Robotics, Autonomous agnets %X This volume is the proceedings of the meeting on May 13, 1997 held in in Daytona, Florida, USA in conjunction with FLAIRS symposium. There is no online version. You must order this from the Dept of CS at the University at Buffalo. Tue, 15 Apr 1997 14:51:03 GMT %U http://www.cse.buffalo.edu/tech-reports/97-04.ps %A Sheikholeslami, Gholamhosein %A ang, Aidong %T A Clustering Approach for Large Visual Databases %R 97-04 %D February 21, 1997 %I Department of Computer Science, SUNY Buffalo %K Image clustering %X The representation and organization of images in a large-scale image database is crucial to support effective and efficient accesses to image data on the basis of content. In this process, significant features must first be extracted from image data in their pixel format. These features must then be classified and indexed to assist efficient retrieval of image content. In this paper, we investigate effective image data representation and organization approaches for large-scale image databases. An effective block-oriented image decomposition structure is used as a fundamental data model for representing image content. A clustering mechanism is then proposed to categorize images based on feature similarity. Efficient image retrieval is supported. Experimental analysis are conducted and presented to demonstrate the effectiveness and efficiency of the approaches. Tue, 15 Apr 1997 14:51:51 GMT %A Walters, Deborah %A Li, Yiming %A Milun, Elyse %A Atanacio, Bemina %T General Ribbons: A Model for Stylus Generated Images %R 97-05 %D May 15, 1997 %I Department of Computer Science, SUNY Buffalo %K General Ribbons, Thinning, Stylus Generated Images, Segmentation %X General ribbons are a mathematical model of stylus generated images which is based on the image formation process. One purpose of the model is to provide a formal basis for the development of thinning algorithms for the stroke components of stylus generated images. Before the stroke components can be thinned they must be segmented from the blob components of the image which do not require thinning. A second purpose of the model is to provide a formal basis for the development of blob/stroke segmentation algorithms. Two blob/stroke segmentation algorithms based on the model are presented. Fri, 16 May 1997 16:45:08 GMT %A Walters, Deborah %A Li, Yiming %A Wright, Ron %T General Ribbons: Generic Blob/stroke Segmentation %R 97-07 %D May 16, 1997 %I Department of Computer Science, SUNY Buffalo %K General Ribbons, Segmentation, Thinning, Stylus-generated Images %X General ribbons are a mathematical model of stylus generated images which is based on the image formation process. One purpose of the model is to provide a formal basis for the development of thinning algorithms for the stroke components of stylus generated images. Before the stroke components can be thinned they must be segmented from the blob components of the image which do not require thinning. A second purpose of the model is to provide a formal basis for the development of blob/stroke segmentation algorithms. This technical report contains the definitions, theorems and proofs on which the generic blob/stroke segmentation algorithm is based. A discussion of the General Ribbon model and other blob/stroke segmentation algorithms can be found in: Walters, Deborah; Li, Yiming; Milun, Elyse; Atanacio, Bemina. General Ribbons: A Model for Stylus Generated Images, CS-UB Technical Report 97-05, May 15, 1997. Tue, 27 May 1997 18:52:27 GMT %U http://www.cse.buffalo.edu/tech-reports/97-08.cogsci.tr.ps %A Ehrlich, Karen %A Rapaport, William J. %T A Computational Theory of Vocabulary Expansion %R 97-08 %D May 5, 1997 %I Department of Computer Science, SUNY Buffalo %K computational linguistics, natural language learning, semantic networks, knowledge representation %X As part of an interdisciplinary project to develop a computational cognitive model of a reader of narrative text, we are developing a computational theory of how natural-language-understanding systems can automatically expand their vocabulary by determining from context the meaning of words that are unknown, misunderstood, or used in a new sense. `Context' includes surrounding text, grammatical information, and background knowledge, but no external sources. Our thesis is that the meaning of such a word *can* be determined from context, can be *revised* upon further encounters with the word, ``*converges*'' to a dictionary-like definition if enough context has been provided and there have been enough exposures to the word, and eventually ``*settles down*'' to a ``steady state'' that is always subject to revision upon further encounters with the word. The system is being implemented in the SNePS knowledge-representation and reasoning system. This document is a slightly modified version (containing the algorithms) of that which is to appear in _Proceedings of the 19th Annual Conference of the Cognitive Science Society (Stanford University)_ (Mahwah, NJ: Lawrence Erlbaum Associates). It is also _Technical Report 97-2_ (Buffalo: SUNY Buffalo Center for Cognitive Science). It is also available on-line at . Tue, 27 May 1997 19:10:31 GMT %U http://www.cse.buffalo.edu/tech-reports/97-09.ps %A Rajiv Chopra %T An Architecture for Exploiting Qualitative Scene-specific Context in High-Level Computer Vision %R 97-09 %D June 1, 1997 %I Department of Computer Science, SUNY Buffalo %K constraint satisfaction; computer vision; interval arithmetic; context based vision; image understanding %X In this dissertation we present an architecture to incorporate collateral information in the high level computer vision task of object location. The declarative specification of the scene hypothesis and the domain independent control algorithm that exploits spatial information to drive the vision process, are two major contributions of this dissertation. This work has been theoretically grounded in constraint satisfaction algorithms. Apart from the application of standard CSP algorithms, several new techniques in constraint satisfaction have been developed. We provide an algorithm that performs consistency filtering for certain types of non-binary constraints. We also present an innovative application of interval arithmetic in constraint satisfaction. Though interval constraint satisfaction is an extensive research area, we believe this to be the first attempt at using interval arithmetic to reduce the domain generation cost of finite domain CSPs. A new algorithm has been proposed here for the above. Illustration with a simple example, analysis and implementation of the algorithm have also been detailed here. We have demonstrated the architecture in three implemented vision systems and have shown that it is simple yet powerful for application in several domains. Tue, 22 Jul 1997 17:16:42 GMT %U http://www.cse.buffalo.edu/tech-reports/97-10.ps %A Cai, Jin-Yi %A Nerurkar, Ajay %A Wu, Min-You %T The Design of Uncheatable Benchmarks Using Complexity Theory %R 97-10 %D July 18, 1997 %I Department of Computer Science, SUNY Buffalo %K benchmarks, complexity theory %X We study uncheatable benchamrks. We present some schemes of their design and implementations. We present two methods to obtain computational advantage in judging performance results. In the first approach, the tester gains a computational advantage via a hidden ``secret,'' which is randomly generated. With the secret information, the tester can know, or can easily compute, the correct answer in advance. This approach is called the Secret Key (SK) method. Secondly, for many problems, verifying the result is easier than computing it. For example, verifying the result of a linear equation solver can be accomplished faster than any known algorithm which computes it. This asymmetry allows the tester an computational advantage over the vendor. This approach is called the Result Verification (RV) method. Tue, 22 Jul 1997 17:19:28 GMT %U http://www.cse.buffalo.edu/tech-reports/97-11.ps %A Fang, Chi %T Deciphering Algorithms for Degraded Document Recognition %R 97-11 %D July 17, 1997 %I Department of Computer Science, SUNY Buffalo %K OCR, document recognition, pattern recognition, deciphering %Y pattern recognition; text processing %X The research presented in this thesis provides new solutions to two fundamental problems in document recognition. The first problem is character segmentation. Touching characters and character fragmentation caused by image degradation are difficult problems for current document recognition systems. The second problem that this thesis addresses is the dependence of today's document recognition systems on extensive font training. These two problems are shown to be the main reasons that cause performance breakdown for most of today's commercial document recognition systems. Our research provides solutions to the two problems by seeking alternative approaches that can recognize degraded documents with high accuracy and robust performance. Reliable performance on degraded documents is achieved by avoiding these two difficult problems in the recognition approaches. We propose to consider the computational task of document recognition as a process of finding the mapping between the visual patterns in the input document and their linguistic identities. Deciphering algorithms are proposed to decode the mapping by combining the visual constraints from the input document and the various levels of linguistic constraints from a language base. This deciphering approach to document recognition works on different levels of language granularities, both on the character level as well as on the word level. Therefore, document recognition can be achieved by decoding characters using character level linguistic constraints. It can also be achieved by the direct decryption of words using word level linguistic constraints. A modified character-level deciphering algorithm is proposed based on an existing research. The modifications to an original algorithm extend a character-level deciphering algorithm to documents that contain touching characters. It also provides a solution to errors in character pattern clustering. A word-level deciphering approach to document recognition is also proposed in this thesis. Word-level language constraints are used to first decrypt the words from a selected portion of the input text that has relatively more reliable word n-gram statistics. Word decryption is considered as a process of constraint satisfaction and is implemented by a probabilistic relaxation algorithm. After the decryption of words in a selected portion of the input text, font information is learned and then used to re-recognize the rest of the input text which was not used for deciphering. The re-recognition of the rest of the input text is achieved by a hypothesis testing algorithm. The applicability of the proposed deciphering approaches to practical document recognition tasks is demonstrated by experimental results of applying the proposed approaches to scanned documents. The test documents used for the experiments contain image degradations including touching characters, character fragmentation, as well as individual character deformations. Tue, 22 Jul 1997 17:21:35 GMT %U http://www.cse.buffalo.edu/tech-reports/97-12.ps %A Hexmoor, Henry %A Cuddihy, Elisabeth %T Performance of a simple cooperative individual situation assessment (CISA) with respect to information sharing strategy metrics %R 97-12 %D July 23, 1997 %I Department of Computer Science, SUNY Buffalo %K multi-agent systems, information sharing Wed, 23 Jul 1997 14:16:29 GMT %U http://www.cse.buffalo.edu/tech-reports/97-13.ps %A Naik, Ashish V. %A Rogers, John, D. %A Royer, James S. %A Selman, Alan L. %T A Hierarchy Based on Output Multiplicity %R 97-13 %D August 05, 1997 %I Department of Computer Science, SUNY Buffalo %K multivavlued functions, nondeterminism, function classes, output multiplicity %X The class NP$k$V consists of those partial, multivalued functions that can be computed by a nondeterministic, polynomial time-bounded transducer that has at most $k$ distinct values on any input. We define the {\em output-multiplicity hierarchy\/} to consist of the collection of classes NP$k$V, for all positive integers $k \geq 1$. In this paper we investigate the strictness of the output-multiplicity hierarchy and establish three main results pertaining to this: 1. If for any $k>1$, the class NP$k$V collapses into the class NP$(k - 1$V, then the polynomial hierarchy collapses to its second level, $\Sigma_2^P$. 2. If the converse of the above result is true, then any proof of this converse cannot relativize. We exhibit an oracle relative to which the polynomial hierarchy collapses to $P^NP$, but the output-multiplicity hierarchy is strict. 3. Relative to a random oracle, the output-multiplicity hierarchy is strict. This result is in contrast to the still open problem of the strictness of the polynomial hierarchy relative to a random oracle. In introducing the technique for the third result we prove a related result of interest: relative to a random oracle $\UP\not=\NP$. Tue, 05 Aug 1997 16:21:03 GMT %U http://www.cse.buffalo.edu/tech-reports/98-01.ps %A Shapiro, Stuart C. %T A Procedural Solution to the Unexpected Hanging and Sorites Paradoxes %R 98-01 %D January 05, 1998 %I Department of Computer Science, SUNY Buffalo %K paradoxes, unexpected hangman, prediction paradoxes, sorites, parallel procedures, procedures %X The paradox of the Unexpected Hanging, related prediction paradoxes, and the sorites paradoxes all involve reasoning about ordered collections of entities: days ordered by date in the case of the Unexpected Hanging; men ordered by the number of hairs on their heads in the case of the bald man version of the sorites. The reasoning then assigns each entity a value that depends on the previously assigned value of one of the neighboring entities. The final result is paradoxical because it conflicts with the obviously correct, commonsensical value. The paradox is due to the serial procedure of assigning a value based on the newly assigned value of the neighbor. An alternative procedure is to assign each value based only on the original values of neighbors---a parallel procedure. That procedure does not give paradoxical answers. Mon, 09 Mar 1998 16:36:35 GMT %U http://www.cse.buffalo.edu/tech-reports/98-02.ps %A Campbell, Alistair E. %A Shapiro, Stuart C. %T Algorithms for Ontological Mediation %R 98-02 %D January 23, 1998 %I Department of Computer Science, SUNY Buffalo %K ontology, agent, miscommunication, mediation, interlingua %X We lay the foundation for ontological mediation as a method for resolving communication difficulties resulting from different ontologies. The notion of hierarchical relations enables a theory of orientation or direction of ontologies to be presented. We describe an ontologcial mediator as being able to think about (or conceptualize) concepts from ontologies and find equivalences between them. Algorithms for finding the meanings of unfamiliar words by asking questions are introduced and evaluated experimentally. Mon, 09 Mar 1998 16:36:42 GMT %U http://www.cse.buffalo.edu/tech-reports/97-14.ps %A Hexmoor, H %A Lopez, F %T Toward Object Selection with a Pointer %R 97-14 %D October 30, 1997 %I Department of Computer Science, SUNY Buffalo %K Object-Selection, Deixis, %X Using a pointer as means of disambiguating objects in the world is discussed. We offer a visual object selection algorithm and a technique for computing pointer effectiveness. We report on relevant assumptions and directions for a research path. Mon, 09 Mar 1998 16:40:55 GMT %U http://www.cse.buffalo.edu/tech-reports/98-03.ps %A Soh, Jung %T A Theory of Document Object Locator Combination %R 98-03 %D March 25, 1998 %I Department of Computer Science, SUNY Buffalo %K document analysis, object location, address block location, combination, Korean mail %X Traditional approaches to document object location use a single locator that is expected to locate as many instances of the object class of interest as possible. However, if the class includes subclasses with diverse visual characteristics or is not characterized by easily computable visual features, it is difficult for the single locator to account for wide variation in object characteristics within the class. As a result, increasingly complex models of objects to be located are used. An alternative approach is to combine the decisions of multiple locators, each of which is suitable for certain image conditions. This approach utilizes a collection of simple locators that complement one another, rather than relying on one complex locator. An effective method for combining the location results is vital to the success of this approach. This thesis presents a theory of combining the results of multiple document object locators tuned to different object characteristics. The purpose of the combination is to achieve integrated location performance which is better than that of any individual locator. Location results are represented by objective confidence values, regardless of their types. This allows for combining locators at any output information level. Since different locators use different segmentation algorithms, multiple decisions on a single object are not readily available. Object equivalence and correspondence are used to determine what decisions to combine. The highest confidence, confidence summation, weighted confidence summation, probabilistic confidence estimation, and fuzzy integral methods are proposed for combining confidence values. A method for dynamic selection of locators based on training image set partitioning is proposed. Differences in locator performance levels are represented by locator relevance values, which are used in a combination method and dynamic selection. Measures for evaluating combination performance are proposed and compared. The theory is applied to the address block location problem. A multiple locator algorithm employing a machine-printed address block locator, a handwritten address block locator, and a clustering-based locator is created and tested on a database of 1,100 mail piece images, in two separate experiments. The experimental results show that combining location results using the theory provides location performance that excels any individual locator performance, and therefore is a viable approach to document object location problems. Mon, 13 Apr 1998 13:33:35 GMT %U http://www.cse.buffalo.edu/tech-reports/98-04.ps %A Hexmoor, H %T Representing and Learning Routine Activities %R 98-04 %D December 1995 %I Department of Computer Science, SUNY Buffalo %K Knowledeg representation, robotics, intelligent agents %X A routine is a habitually repeated performance of some actions. Agents use routines to guide their everyday activities and to enrich their abstract concepts about acts. This dissertation addresses the question of how an agent who is engaged in ordinary, routine activities changes its behavior over time, how the agent's internal representations about the world is affected by its interactions, and what is a good agent architecture for learning routine interactions with the world. In it, I develop a theory that proposes several key processes: (1) automaticity, (2) habituation and skill refinement, (3) abstraction-by-chunking, and (4) discovery of new knowledge chunks. The process of automaticity caches the agent's knowledge about actions into a flat stimulus-response data structure that eliminates knowledge of action consequences. The stimulus-response data structure produces a response to environmental stimuli in constant time. The process of habituation and skill refinement uses environmental clues as rewards. Rewards are used to develop a bias for the agent's actions in competing action-situation pairs where the agent did not have prior choices. The process of abstraction-by-chunking monitors the agent's increased reliance on stimulus-response data structures and turns the agent's complex actions into primitive acts, thereby eliminating the need for the agent to elaborate its plans beyond a certain level. The process of discovering knowledge-chunks monitors the agent's use of stimulus-action data structures and constructs knowledge about action preconditions and consequences and constructs patterns of interactions into plans. I have implemented several agents that demonstrate parts of my theory using an agent architecture I developed called GLAIR. GLAIR models agents that function in the world. Beyond my theory about routines, GLAIR is used to demonstrate situated actions as well as deliberative actions. Each of GLAIR's three levels (Sensori-actuator, Perceptuo-motor, and Knowledge) uses different representations and models different components of intelligent agency. GLAIR levels operate semi-autonomously. Whereas intra-level learning improves an agent's performance, inter-level learning migrates know-how from one level to another. Using the GLAIR architecture, I model agents that engage in routines, use these routines to guide their behavior, and learn more concepts having to do with acts. The significance of my theory, architectures, and the agents are to illustrate that computational agents can autonomously learn know-how from their own routine interactions in the world as well as learn to improve their performance. Fri, 22 May 1998 15:34:33 GMT %U http://www.cse.buffalo.edu/tech-reports/97-15.ps %A Rapaport, William J. %T Implementation Is Semantic Interpretation %R 97-15 %D November 21, 1997 %I Department of Computer Science, SUNY Buffalo %K implementation, individuation, instantiation, reduction, supervenience, semantic interpretation %X What is the computational notion of ``implementation''? It is not individuation, instantiation, reduction, or supervenience. It is, I suggest, semantic interpretation. Mon, 20 Jul 1998 14:05:05 GMT %U http://www.cse.buffalo.edu/tech-reports/98-06.ps %A Slavik, Petr %T Approximation Algorithms for Set Cover and Related Problems %R 98-06 %D April 30, 1998 %I Department of Computer Science, SUNY Buffalo %K Approximation Algorithms, Combinatorial Optimization, Errand Scheduling, Generalized Traveling Salesman Problem, Group Steiner Tree Problem, Partial Set Cover, Set Cover, Tree Cover Problem %X In this thesis, we analyze several known and newly designed algorithms for approximating optimal solutions to NP-hard optimization problems. We give a new analysis of the greedy algorithm for approximating the SET COVER and PARTIAL SET COVER problems obtaining significantly improved performance bounds. We also give a first approximation algorithm with a non-trivial performance bound for the ERRAND SCHEDULING and TREE COVER problems, known also as the GENERALED TRAVELING SALESMAN and GROUP STEINER TREE problems. The main results of this thesis first appeared in my papers [87], [89], [91], and [90]; and in my technical reports [86] and [88]. Mon, 20 Jul 1998 14:08:48 GMT %U http://www.cse.buffalo.edu/tech-reports/98-05.ps %A Rapaport, William J. %A Ehrlich, Karen %T A Computational Theory of Vocabulary Acquisition %R 98-05 %D April 14, 1998 %I Department of Computer Science, SUNY Buffalo %K computational linguistics, vocabulary acquisition, machine learning %X As part of an interdisciplinary project to develop a computational cognitive model of a reader of narrative text, we are developing a computational theory of how natural-language-understanding systems can automatically acquire new vocabulary by determining from context the meaning of words that are unknown, misunderstood, or used in a new sense. `Context' includes surrounding text, grammatical information, and background knowledge, but no external sources. Our thesis is that the meaning of such a word *can* be determined from context, can be *revised* upon further encounters with the word, ``*converges*'' to a dictionary-like definition if enough context has been provided and there have been enough exposures to the word, and eventually ``*settles down*'' to a ``steady state'' that is always subject to revision upon further encounters with the word. The system is being implemented in the SNePS knowledge-representation and reasoning system. This essay is forthcoming as a chapter in Iwanska, Lucja, & Shapiro, Stuart C. (1999), _Natural Language Processing and Knowledge Representation: Language for Knowledge and Knowledge for Language_ (Menlo Park, CA/Cambridge, MA: AAAI Press/MIT Press). Mon, 20 Jul 1998 14:10:55 GMT %U http://www.cse.buffalo.edu/tech-reports/96-26.ps %A Rapaport, William J. %T Understanding Understanding: Semantics, Computation, and Cognition %R 96-26 %D July 17, 1996 %I Department of Computer Science, SUNY Buffalo %K syntax, semantics, cognition, computation, Chinese Room Argument, conceptual role semantics, holism, implementation, natural-language understanding, methodological solipsism, Helen Keller %Y I.2 ARTIFICIAL INTELLIGENCE; I.2.4 Knowledge Representation Formalisms and Methods ;I.2.7 Natural Language Processing; %X What does it mean to understand language? John Searle once said: "The Chinese Room shows what we knew all along: syntax by itself is not sufficient for semantics. (Does anyone actually deny this point, I mean straight out? Is anyone actually willing to say, straight out, that they think that syntax, in the sense of formal symbols, is really the same as semantic content, in the sense of meanings, thought contents, understanding, etc.?)." Elsewhere, I have argued "that (suitable) purely syntactic symbol-manipulation of a computational natural-language-understanding system's knowledge base suffices for it to understand natural language." The fundamental thesis of the present book is that understanding is recursive: "Semantic" understanding is a correspondence between two domains; a cognitive agent understands one of those domains in terms of an antecedently understood one. But how is that other domain understood? Recursively, in terms of yet another. But, since recursion needs a base case, there must be a domain that is not understood in terms of another. So, it must be understood in terms of itself. How? Syntactically! In syntactically understood domains, some elements are understood in terms of others. In the case of language, linguistic elements are understood in terms of non-linguistic ("conceptual") yet internal elements. Put briefly, bluntly, and a bit paradoxically, semantic understanding is syntactic understanding. Thus, any cognitive agent--human or computer--capable of syntax (symbol manipulation) is capable of understanding language. The purpose of this book is to present arguments for this position, and to investigate its implications. Subsequent chapters discuss: models and semantic theories (with critical evaluations of work by Arturo Rosenblueth and Norbert Wiener, Brian Cantwell Smith, and Marx W. Wartofsky); the nature of "syntactic semantics" (including the relevance of Antonio Damasio's cognitive neuroscientific theories); conceptual-role semantics (with critical evaluations of work by Jerry Fodor and Ernest Lepore, Gilbert Harman, David Lewis, Barry Loewer, William G. Lycan, Timothy C. Potts, and Wilfrid Sellars); the role of negotiation in interpreting communicative acts (including evaluations of theories by Jerome Bruner and Patrick Henry Winston); Hilary Putnam's and Jerry Fodor's views of methodological solipsism; implementation and its relationships with such metaphysical concepts as individuation, instantiation, exemplification, reduction, and supervenience (with a study of Jaegwon Kim's theories); John Searle's Chinese-Room Argument and its relevance to understanding Helen Keller (and vice versa); and Herbert Terrace's theory of naming as a fundamental linguistic ability unique to humans. Throughout, reference is made to an implemented computational theory of cognition: a computerized cognitive agent implemented in the SNePS knowledge-representation and reasoning system. SNePS is: symbolic (or "classical"; as opposed to connectionist), propositional (as opposed to being a taxonomic or "inheritance" hierarchy), and fully intensional (as opposed to (partly) extensional), with several types of interrelated inference and belief-revision mechanisms, sensing and effecting mechanisms, and the ability to make, reason about, and execute plans. Thu, 17 Sep 1998 18:46:39 GMT %U http://www.cse.buffalo.edu/tech-reports/97-16.ps %A Liao, Min-Hung %T Chinese to English Machine Translation Using SNePS as an Interlingua %R 97-16 %D December 1, 1997 %I Department of Computer Science and Engineering, SUNY Buffalo %K machine translation, interlingua, semantic networks %X An interlingua machine translation is a two-stage operation: from source language to an interlingua, and from the interlingua to the target language. The idea of translating natural-language texts using an interlingua, an intermediate common language, is based on the belief that while languages differ greatly in surface structures, they share a common deep structure. I propose a way of automatically translating texts using SNePS as an interlingua. The representation of the meaning of the source-language input is intended to be language-independent, and this same representation is used to synthesize the target-language output. As an interlingua, SNePS fulfills the requirements of being formal, language-independent, and a powerful medium for representing meaning; thus, it can handle ambiguities. SNePS can be used to translate texts automatically as follows. The user inputs a sentence of the source language to a generalized augmented-transition-network (GATN) parser-generator. The parser fragment of the GATN parser-generator updates an existing knowledge base containing semantic networks to represent the system's understanding of the input sentence. The node newly built to represent the proposition is then passed to the generator fragment of the GATN parser-generator, which generates a sentence of the target language expressing the proposition in the context of the knowledge base. The parsing of Chinese relies more on semantic information than syntactic relations because, first, the word order is determined primarily by semantic factors rather than syntactic ones, second, there is a lack of morphological inflections and syntactic clues. A series of noun phrases and verb phrases can be juxtaposed without syntactic glues such as function words or variation of verb forms to make the linking. These linguistic properties cause lexical and structural ambiguities. Besides being an adequate interlingua representation, SNePS is also a computational environment particularly suitable for processing Chinese because it provides the facilities for building, retrieving, and deducing semantic information that guides the parsing and resolves ambiguities. Mon, 30 Nov 1998 21:54:44 GMT %U http://www.cse.buffalo.edu/tech-reports/98-09.ps %A Ogihara, Mitusnori %A Regan, Kenneth W. %A Toda, Seinosuke %T Graded Self-Reducibility %R 98-09 %D December 30, 1998 %I Department of Computer Science and Engineering, SUNY Buffalo %K Computational complexity, time and space complexity, self-reducibility %X We introduce two special kinds of self-reducible sets that we call {\em time-graded\/} and {\em space-graded\/} languages. Attaching time and space bounds to them yields a uniform, quantitative definition of resource-bounded self-reducibility that applies to all languages. We apply this to study the relationship between $\NSPACE[s(n)]$ and $\DSPACE[s(n)^2]$, emphasizing the case $s(n) = O(\log n)$. We show that the class of logspace-graded languages, which is contained in $\DSPACE[\log^2 n]$, contains not only $\NL$ and uniform $\NC^2$, but also a class of Aux-PDA languages that is not known to be a subclass of $\P$. We also prove that many-one space-graded classes are many-one equivalent to the special case in which the self-reduction makes one query to a string of strictly shorter length. For this latter idea of ``instance contraction,'' we note that some $\NL$-complete problems admit $n$-to-$n/2$ contraction in logspace, and prove that some $\NC^1$-complete problems are $n$-to-$n/2$ contractible by finite automata that involve only parity counting. Thu, 31 Dec 1998 15:40:55 GMT %U http://www.cse.buffalo.edu/tech-reports/99-01.ps %A Lee, Chain-Wu %T TERRESA: A Task-Based Message-Driven Parallel Semantic Network System %R 99-01 %D January 30, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K parallel computation, artificial intelligence, semantic network %X The ultimate goal of research in artificial intelligence is to build a system with human intelligence. Yet, despite considerable effort, artificial intelligence systems are still a long way from that goal. Various reasons attribute to why the goal cannot be achieved at current stage, one of the reasons is the vast amount of information to be processed. When presented with real world domains of millions of concepts and assertions, almost all existing systems are unable to deliver the results within a reasonable amount of time. This dissertation describes a parallel semantic network system, TERRESA, based on SNePS. TERRESA is a task-based, message-driven, multithreaded parallel semantic network system with the support of shared knowledge, load balancing and duplicate checking on MIMD distributed memory/message passing systems. TERRESA can be split into two collaborating components: the host module and the slave module. The host module interacts with the user and processes the information for the slaves, while the slave module performs task execution. The current version of TERRESA focuses on SNePS path-based inference only. TERRESA is designed to be portable among different parallel machines, and therefore most of the system dependent functions are either avoided or re-implemented. TERRESA is written in ANSI C and MPI (Message Passing Interface) library with the help of flex lexical analyzer and yacc parser generator. Porting TERRESA to a new platform only requires recompiling in most cases. The performance studies of TERRESA have been done on SUN multiprocessor server. Mon, 26 Apr 1999 14:13:48 GMT %U http://www.cse.buffalo.edu/tech-reports/99-03.ps %A Yu D. %A Sheikholeslami S. %A ang, A. %T FindOut: Finding Outliers in Very Large Datasets %R 99-03 %D May 05, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K Data Mining, Database, Multidimensional data %X Signal processing techniques have been introduced to transform images for image enhancement, filtering and restoration, analysis, and reconstruction. In this paper, we apply signal processing techniques to solve important KDD problems. In particular, we introduce a novel deviation (or outlier) detection approach, termed {\it FindOut}, based on wavelet transform. The main idea in FindOut is to remove the clusters from the original data and then identify the outliers. Although previous research showed that such techniques may not be effective because of the nature of the clustering, FindOut can successfully identify various percentages of outliers from large datasets. Thus, we can combine both clustering and outliers detection in a unified approach. Experimental results on very large datasets are presented which show the efficiency and effectiveness of the proposed approach. Thu, 01 Jul 1999 17:50:00 GMT %U http://www.cse.buffalo.edu/tech-reports/99-04.ps %A Yu, D. %A ang, A. %T ACQ: An Automatic Clustering and Querying Approach for Large Image Databases %R 99-04 %D May 05, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K data mining %X Large image collections such as web-based image databases are being built in various locations. Because of the diversity of such image data collections, clustering images becomes an important and non-trivial problem. Such clustering tries to find the densely populated regions in the feature space to be used for efficient image retrieval. In this paper, we present an automatic clustering and querying ACQ approach for large image databases. Our approach can efficiently detect clusters of arbitrary shape. It does not require the number of clusters to be known a priori and is insensitive to the noise (outliers) and the order of input data. Based on this clustering approach, efficient image querying is supported. Experiments demonstrate the effectiveness and efficiency of the approach. Thu, 01 Jul 1999 17:51:24 GMT %U http://www.cse.buffalo.edu/tech-reports/99-05.ps %A Qiao, C. %A Jeong, M. %A Guha, A. %A ang, X. %A Wei, J. %T WDM Multicasting in IP over WDM Networks %R 99-05 %D May 1, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K multicasting, Wavelength division multiplexing (WDM), Internet Protocol (IP), DVMRP, optical burst switching, %X Supporting WDM multicasting in an IP over WDM network poses interesting problems because some WDM switches may be incapable of switching an incoming signal to more than one output interface. An approach to WDM multicasting based on wavelength-routing, which constructs a multicafor each multicast session so that multicast-incapable WDM switches do not need to multicast, was proposed and evaluated in one of our previous study. Such an approach requires global knowledge of the WDM layer. In this paper, we study WDM multicasting in an IP over WDM network under the framework of Multiprotocol Label Switching (MPLS) using optical burst/label switching (OBS/OLS). We propose a protocol which modifies a multicast tree constructed by distance vector multicast routing protocol (DVMRP) into a multicast forest based on the local information only. Thu, 01 Jul 1999 17:53:58 GMT %U http://www.cse.buffalo.edu/tech-reports/99-06.ps %A Rapaport, William J. %T How to Pass a Turing Test: Syntax Suffices for Understanding Natural Language %R 99-06 %D June 08, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K Turing Test, Chinese Room Argument, syntax, semantics %X A theory of "syntactic semantics" is advocated as a way of understanding how computers can think (and how the Chinese-Room-Argument objection to the Turing Test can be overcome): (1) Semantics, as the study of relations between symbols and meanings, can be turned into syntax---a study of relations among symbols (including meanings)---and hence syntax can suffice for the semantical enterprise. (2) Semantics, as the process of understanding one domain modeled in terms of another, can be viewed recursively: The base case of semantic understanding---understanding a domain in terms of itself---is syntactic understanding. An internal (or "narrow"), first-person point of view makes an external (or "wide"), third-person point of view otiose for purposes of understanding cognition. The paper also sketches the ramifications of this view with respect to methodological solipsism, conceptual-role semantics, holism, misunderstanding, and implementation, and looks at Helen Keller as inhabitant of a Chinese Room. Thu, 01 Jul 1999 17:55:07 GMT %U http://www.cse.buffalo.edu/tech-reports/99-02.ps %A Fortnow, L. %A Pavan, A. %A Selman, A. %T Distributionally-Hard Languages %R 99-02 %D April 26, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K average-case complexity, P-bi-immune, P-printable, distributionally-hard %Y F.1.2;F.1.3 %X Define a set $L$ to be {\em distributionally-hard to recognize} if for every polynomial-time computable distribution $\mu$ with infinite support, $L$ is not recognizable in polynomial time on the $\mu$-average. Cai and Selman defined a modification of Levin's notion of average polynomial time and proved that every P-bi-immune language is distributionally-hard. Pavan and Selman proved that there exist distributionally-hard sets that are not P-bi-immune if and only P contains P-printable-immune sets. We extend this characterizion to include assertions about several traditional questions about immunity, about finding witnesses for NP-machines, and about existence of one-way functions. Similarly, we address the question of whether NP contains sets that are distributionally hard. Several of our results are implications for which we cannot prove whether or not their converse holds. In nearly all such cases we provide oracles relative to which the converse fails. We use the techniques of Kolmogorov complexity to describe our oracles and to simplify the technical arguments. Thu, 01 Jul 1999 18:01:27 GMT %U http://www.cse.buffalo.edu/tech-reports/99-07.ps %A Burhans, Debra T. %A Shapiro, Stuart C. %T Expanding the Notion of Answer in Rule-Based Systems %R 99-07 %D November 08, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K question answering, resolution theorem proving %Y I.2.4 Knowledge Representation Formalisms and Methods %X The traditional notion of a question in AI is an open sentence Q(x1..xn), and the traditional notion of an answer is a set of a1...an such that Q(a1...an). More recently, this notion of answer has been extended to generic answers of the form All(x1...xn)[G(x1...xn) => Q(x1...xn)]. We further extend the notion of answer to include hypothetical/generic answers of the form (Exists(w1...wn1)H(w1...wn1)) => All(x1...xn2, y1...yn3)[G(x1...xn2, y1...yn3) => All(z1...zn4)Q(x1...xn2, z1...zn4)]. We formally show how every clause generated during the course of a refutation resolution procedure may be analyzed as a hypothetical/generic answer, as long as it descends from the query clause. Informally, in the above schema: Q, the specific part of the answer, represents literals that were part of the query; G, the generic part, represents literals that share variables with the Q literals, or that share variables with other G literals; and H, the hypothetical part, represents literals whose variables don't occur in either G or Q. Each part may also contain constants that were or weren't part of the query. Tue, 18 Jan 2000 16:02:01 GMT %U http://www.cse.buffalo.edu/tech-reports/98-10.ps %A Shapiro, Stuart C. %T Belief Revision and Truth Maintenance Systems: An Overview and a Proposal %R 98-10 %D December 31, 1998 %I Department of Computer Science and Engineering, SUNY Buffalo %K Belief revision; truth maintenance; truth maintenance systems %Y Nonmonotonic reasoning and belief revision; Knowledge Representation Formalisms and Methods %X This paper presents a very high-level introduction to Belief Revision and Truth Maintenance Systems, including explanations of basic terminology, a brief history, and a comment on the two literatures: the TMS literature, and the AGM Belief Revision literature. More extensive surveys in each of the two literatures are cited. The paper concludes with a proposal to continue the investigation of the two traditions, and to see how they might be brought together. Tue, 25 Jan 2000 15:18:05 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-02.ps %A Johnson, Frances L. %A Shapiro, Stuart C. %T Formalizing a Deductively Open Belief Space %R 2000-02 %D January 24, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K knowledge; belief; belief space; knowledge representation; belief revision; belief change; beliefs %Y Knowledge Representation Formalisms and Methods %X A knowledge representation and reasoning system must be able to deal with contradictions and revise beliefs. There has been much research in belief revision in the last decade, but this research tends to be either in the Coherence camp (AGM) or the Foundations (TMS) camp with little crossover. Most theoretical postulates on belief revision and belief contraction assume a deductively closed belief space - something that is computationally hard (or impossible) to produce in an implementation. This makes it difficult to analyze implemented belief revision systems using the theoretical postulates. This paper offers a formalism that describes a deductively open belief space (DOBS). It then uses this formalism to alter the AGM integrity constraints for a DOBS. A DOBS uses a base set of hypotheses, but only deduces beliefs from that base as the result of specific queries. Thus, it can grow over time even if the base remains static, and can never be referred to as consistent - only either inconsistent or "not known to be inconsistent." This work and future alterations to the traditional postulate formalisms will better enable system/postulate comparisons. Mon, 06 Mar 2000 19:51:39 GMT %U http://www.cse.buffalo.edu/tech-reports/99-09.ps %A Johnson, Frances L. %A Shapiro, Stuart C. %T Finding and Resolving Contradictions in a Battle Scenario %R 99-09 %D September 09, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K knowledge representation; contradictions; belief; belief revision; beliefs; autoBR; automatic; %Y Nonmonotonic reasoning and belief revision %X This report presents an initial attempt to run a battle scenario with built in inconsistencies on the SNePS knowledge representation and reasoning system. This system alerts the user to the inconsistencies as soon as they are detected and offers an opportunity to correct the base hypotheses as well and, consequently, the beliefs that were derived from them. In this scenario, automatic belief revision is able to narrow down its culprit choices to one proposition each time it is called, so it removes those propositions. The system automatically stops believing any derived beliefs whose justifications rely on the removed beliefs. Tue, 07 Mar 2000 14:14:53 GMT %U http://www.cse.buffalo.edu/tech-reports/99-08.ps %A Johnson, Frances L. %A Shapiro, Stuart C. %T Says Who? -- Incorporating Source Credibility Issues into Belief Revision %R 99-08 %D July 31, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K knowledge representation; knowledge; belief; belief revision; automatic; beliefs; source; credibility; ordering %Y Nonmonotonic reasoning and belief revision; Representations (procedural and rule-based); Semantic networks %X We discuss some belief revision theories and the implementation of some of them in SNeBR, the belief revision subsystem of the SNePS knowledge representation and reasoning system. The following guidelines are important to belief revision: - minimize information removal - retract less-plausible beliefs before more-plausible ones. Alterations to SNeBR that provide users with information to help them follow these guidelines include the incorporation of sources into the knowledge base, as well as ordering of both sources and individual propositions, allowing partially ordered propositional epistemic entrenchment. We also developed an automatic belief revision option that performs the retraction of a belief if one culprit can be singled out based on the guidelines above. Tue, 07 Mar 2000 14:14:55 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-03.ps %A Johnson, Frances L. and Shapiro, Stuart C. %T Implementing Integrity Constraints in an Existing Belief Revision System %R 2000-03 %D March 08, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K knowledge, representation, belief revision, belief, beliefs, integrity constraints, SNePS, autoBR, DOBS %Y Artificial Intelligence;Knowledge Representation;Nonmonotonic reasoning and belief revision %X SNePS is a mature knowledge representation, reasoning, and acting system that has long contained a belief revision subsystem, called SNeBR. SNeBR is triggered when an explicit contradiction is introduced into the SNePS belief space, either because of a user's new assertion, or because of a user's query. SNeBR then makes the user decide what belief to remove from the belief space in order to restore consistency, although it provides information to help the user in making that decision. We have recently added automatic belief revision to SNeBR, by which, under certain circumstances, SNeBR decides by itself which belief to remove, and then informs the user of the decision and its consequences. We have used the well-known belief revision integrity constraints as a guide in designing automatic belief revision, taking into account, however, that SNePS's belief space is not deductively closed, and that it would be infeasible to form the deductive closure in order to decide what belief to remove. This paper briefly describes SNeBR both before and after this revision, discusses how we adapted the integrity constraints for this purpose, and gives an example of the new SNeBR in action. Mon, 13 Mar 2000 13:47:07 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-04.ps %A Slavik, Petr %T Slice Distance %R 2000-04 %D April 08, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K handwriting recognition, minimum edit distance, slice distance, dynamic programming, word recognition %Y I.5.4 %X We introduce a novel way of computing an image-independent recognizer-dependent distance between ASCII words. This distance is a natural generalization of the minimum edit distance in the context of handwriting recognition. It is based on confusion matrices for only parts of characters called character ``slices''. This ``slice distance'' naturally explains the confusions and misrecognitions encountered in recognition of handwritten words and phrases by a particular recognizer and could be used to exploit both the weak and the strong points of the recognizer. Even though we describe the techniques for computing the slice distance using an example of a particular word recognizer, our methods can be easily generalized to almost any segmentation-based handwritten-word recognition system. Mon, 24 Apr 2000 13:29:54 GMT %U http://www.cse.buffalo.edu/tech-reports/99-10.ps %A Ismail, Haythem O. %A Shapiro, Stuart C. %T Cascaded Acts: Conscious Sequential Acting for Embodied Agents %R 99-10 %D November 1, 1999 %I Department of Computer Science and Engineering, SUNY Buffalo %K Acting, telicity, cognitive robotics, knowledge representation %Y I.2.4---Knowledge representation formalisms and methods %X A cognitive agent is expected to use awareness of the environment and its own body to direct its actions. Such awareness is required for the simplest and most common type of composite acts: sequences. To perform a sequence of acts, a cognitive agent should start performing one step when, and only when, it comes to believe that the previous one has been completed. We present a model for interleaving action, reasoning, and perception in order to allow for the conscious performance of sequences of acts. To define such a model, the notion of act completion needs to be characterized. This is achieved by developing a formal system in which acts are classified along the dimensions of telicity and primitiveness. The proposed system includes and go beyond the traditional binary telic/atelic distinction. Fri, 28 Apr 2000 17:46:19 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-05.ps %A Jayaraman, Bharat %A Tambay, Pallavi Y %T Constrained Objects for Modeling Complex Systems %R 2000-05 %D April 1, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K Object-Oriented Modeling, Conditional and Quantified Constraints, Preferences, Constraint Solving, Engineering Design, Document Layout %Y Languages %X The goal of this research is to develop a programming language and execution environment for modeling complex engineering entities. We propose to model complex systems using a compositional approach. The building blocks in this approach are objects whose internal states must obey a set of invariants, or constraints. When such objects are aggregated to form a complex object, their internal states might further have to satisfy interface constraints. This paradigm of objects is referred to as constrained objects, and may be regarded as a declarative form of object-oriented programming. We propose to extend earlier work by providing a richer language, called Cob, for specifying constrained objects: We support both the notion of conditional constraints, preferences, and logic variables at the modeling level, and the computational model provides constraint satisfaction, optimization, and incremental recomputation. Cob will be an expressive tool for applications arising in engineering, information and organizational modeling. Tue, 09 May 2000 00:09:00 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-06.ps %A McKernan, Timothy %A Jayaraman, Bharat %T CobWeb: Constrained XML for the Web %R 2000-06 %D May 19, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K constraint xml database %X XML is helping to advance the notion of using the web as a large database. XML can help view, store, manipulate, and transfer semi-structured data that exist in files - often webpages. XML is being developed in part because of the recognized need for a less ad hoc method of handling data than HTML allows. In support of the idea that the web is to be treated like a database, we introduce constraints to XML. Constraints allow for more specific data definitions then XML currently supports, and these definitions may span across multiple webpages across the web. We also define more data types, so that declaring constraints can be more easily facilitated. Fri, 19 May 2000 17:42:20 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-01.ps %A Shapiro, Stuart C. %A Johnson, Frances L. %T Automatic Belief Revision in SNePS %R 2000-01 %D March 03, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K Belief Revision; Knowledge Representation; Reasoning %Y Knowledge Representation Formalisms and Methods %X SNePS is a logic- and network- based knowledge representation, reasoning, and acting system, based on a monotonic, paraconsistent, first-order term logic, with compositional intensional semantics. It has an ATMS-style facility for belief contraction, and an acting component, including a well-defined syntax and semantics for primitive and composite acts, as well as for ``rules'' that allow for acting in support of reasoning and reasoning in support of acting. SNePS has been designed to support natural language competent cognitive agents. When the current version of SNePS detects an explicit contradiction, it interacts with the user, providing information that helps the user decide what to remove from the knowledge base in order to remove the contradiction. The forthcoming SNePS~2.6 will also do automatic belief contraction if the information in the knowledge base warrents it. Mon, 19 Jun 2000 15:24:58 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-07.ps %A Denis, Charles %A Regan, Kenneth %T On Arithmetical Formulas Whose Jacobians are Groebner Bases %R 2000-07 %D July 13, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K polynomial, ideal, Groebner basis, Jacobian, computational complexity %X We exhibit classes of polynomials whose sets of k-th partial derivatives form Groebner bases for all k, with respect to all term orders. The classes are defined by syntactic constraints on arithmetical formulas defining the polynomials. Read-once formulas without constants have this property for all k, while those with constants have a weaker ``Groebner-bounding'' property introduced here. For k = 1 the same properties hold even with arbitrary powering of subterms of the formulas. Fri, 14 Jul 2000 19:59:10 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-08.ps %A Xin He %T A Simple Linear Time Algorithm for Proper Box Rectangular Drawing of Plane Graphs %R 2000-08 %D August 10, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K Graph Drawing, Algorithms %X In this paper we introduce a new drawing style of a plane graph G, called "proper box rectangular" (PBR) drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the "box rectangular" (BR) drawing defined by Rahman, Nakano and Nishizeki. Our method can be adapted to provide a new simpler algorithm for solving the BR drawing problem. Fri, 18 Aug 2000 15:19:24 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-10.ps %A Charles, Denis %T Sieve Methods %R 2000-10 %D July 18, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K Sieves, Bombieri's Theorem, Brun-Titchmarsh Theorem, Squarefree numbers, Distribution of Primes. %X There are many open problems regarding the distribution of primes, for example the {\em Goldbach} conjecture that every even number $ > 2$ is a sum of two primes, the {\em Twin prime} problem that there are infinitely many prime pairs $(p,p+2)$. Sieve methods were developed as a tool to attack these problems and they have become remarkably useful in many other situtations. Sieve methods have shown for example that there are infinitely many primes $p$ such that $p+2$ is a product of at most two prime factors. In our work we show a wide variety of applications where Sieve methods give the best known results; in particular we use Sieves to study the distribution of {\em Square-free} numbers, {\em Smooth numbers}, {\em Quasi-primes}, and primes in short intervals. We also derive Bombieri's theorem using the {\em Large sieve} and use this to prove for example that there are infinitely many primes $p$ such that $p+k$ is squarefree for any $k > 0$, and a product of at most 7 distinct primes. Tue, 05 Sep 2000 01:48:21 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-09.ps %A Petr Slavik and Venu Govindaraju %T An Overview of Run-length Encoding of Handwritten Word Images %R 2000-09 %D August 25, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %K Handwriting Recognition, Image Representation, Image Processing, Run-Length Encoding %Y I.4; I.5 %X Analysis of handwritten word images is closely tied to the method of representing the images. Different representations have their own sets of advantages and disadvantages. In this paper, we propose a novel method of encoding handwritten images using vertical runs that significantly simplifies the implementation of several image-processing tasks pertaining to handwriting recognition. We demonstrate the advantages of both horizontal and vertical run-length encoding schemes and compare them to other widely used representations like chain-code and bitmap. We illustrate ease of use of horizontal runs for correcting the slant angle, image smoothing, and base-line detection and vertical runs for correcting the skew angle and character segmentation. We believe this paper will serve as a useful tutorial in image representation schemes used in handwriting analysis and recognition. Mon, 02 Oct 2000 16:35:42 GMT %U http://www.cse.buffalo.edu/tech-reports/2000-11.ps %A Charles, D. %A Pavan, A. %A Sengupta, S. %T On higher Arthur-Merlin classes %R 2000-11 %D December 12, 2000 %I Department of Computer Science and Engineering, SUNY Buffalo %X We study higher Arthur-Merlin classes defined via several natural probabilistic operators BP, R and coR. We investigate the complexity classes they define, and a number of interactions between these operators and the standard polynomial time hierarchy. Wed, 20 Dec 2000 13:25:31 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-01.ps %A Boxer, Laurence %A Haralick, Robert %T Even faster point set pattern matching in 3-d %R 2001-01 %D January 09, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Point Set Pattern Matching, congruence, %Y ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY; Geometrical problems and computations %X Recent papers concerned with the Point Set Pattern Matching Problem (PSPM) (finding all congruent copies of a pattern in a sample set) in Euclidean 3-space, $R^3$, have given algorithms with running times that have decreased as known output bounds for the problem have decreased. In this paper, a recent result of Akutsu, et al., is used to show that the volume of the output is $O(kn^{1.8}[\log^* n]^{O(1)})$, where $k$ is the size of the pattern and $n$ is the size of the sample set. This is a smaller output bound than was previously known, and makes possible faster running times than were previously known for this problem. We show that with mild additional restrictions on the input (roughly, that the sample set is not too dense or the pattern set is not too small relative to the sample set), our solutions have running times bounded by the time to sort the volume of data given by our output bounds, on sequential computers and on a coarse-grained multicomputer (CGM). Solutions to related problems are also discussed. Thu, 11 Jan 2001 02:48:58 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-02.ps %A Pavan, A. %A Selman, A.L. %T Separation of NP-completeness Notions %R 2001-02 %D January 16, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %X We use hypotheses of structural complexity theory to separate various NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is $\T$-complete but not $\tt$-complete. We provide fairly thorough analyses of the hypotheses that we introduce. Thu, 18 Jan 2001 03:59:39 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-04.ps %A Charles, Denis X. %T A Note on the Subgroup Membership Problem for PSL(2,p) %R 2001-04 %D March 27, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Group Theory; Finite Groups; PSL(2,p) %X We show that there are infinitely many primes $p$ such that the Subgroup Membership Problem for $PSL(2,p)$ belongs to $NP \cap coNP$. -------------------------------------------- Managed by Request Tracker Fri, 30 Mar 2001 13:52:54 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-03.ps %A Bhadra, Debangshu %A Garg, Ashim %T An Interactive Visual Framework for Detecting Clusters of a Multidimensional Dataset %R 2001-03 %D March 27, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K visualization, data mining, cluster, databases, interactive, animation, graphics %X A key problem in data mining applications is that of detecting clusters, i.e., groups of closely related data items, of a multidimensional dataset. Users are adept at detecting clusters in visually presented information. We, therefore, present an interactive framework that allows a user to visualize a multidimensional dataset, and detect clusters in it by repeatedly changing its visualization using interactive operations such as parameter re-adjustment, zooming, subset selection, and cluster probing. Our experiments also suggest that animation provides important clues in detecting clusters. -------------------------------------------- Managed by Request Tracker Fri, 30 Mar 2001 14:40:30 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-05.ps.gz %A Cha, Sung-Hyuk %T Use of Distance Measures in Handwriting Analysis %R 2001-05 %D March 28, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %X Algorithmic analysis of human handwriting has many applications such as in on-line & off-line handwriting recognition, writer verification, etc. Each of these tasks involves comparison of different samples of handwriting. To compare two samples of handwriting requires distance measures. In this dissertation, several new and old distance measures appropriate for handwriting analysis are given. They include element, histogram, probability density function, string, and convex hull distances. Results comparing newly defined histogram and string distance measures with conventional measures are given. We present several theoretical results and describe applications of the methods to the domain of on-line & off-line character recognition and writer verification.

The theoretical results pertain to individuality validation. In classification problems such as writer, face, finger print or speaker identification, the number of classes is very large or unspecified. To establish the inherent distinctness of the classes, i.e., validate individuality, we transform the many class problem into a dichotomy by using a ``distance'' between two samples of the same class and those of two different classes. Based on conjectures derived from experimental observations, we present theorems comparing polychotomy in feature domain and dichotomy in distance domain from the view point of tractability vs. accuracy.

The practical application issues include efficient search, writer identification and discovery. First, fast nearest-neighbor algorithms for distance measures are given. We also discuss designing and analyzing an algorithm for writer identification for a known number of writers and its relationship to handwritten document image indexing and retrieval. Finally, we present mining a database consisting of writer data and features obtained from a handwriting sample, statistically representative of the US population, for feature evaluation and to determine similarity of a specific group of people. Tue, 15 May 2001 13:12:09 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-06.ps %A Chun-Hsi Huang %T Communication-Efficient Bulk Synchronous Parallel Algorithms %R 2001-06 %D July 30, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K parallel algorithm %Y algorithms %X Communication has been pointed out to be the major bottleneck for the performance of parallel algorithms. Theoretical parallel models such as PRAM have long been questioned due to the fact that the theoretical algorithmic efficiency does not provide a satisfactory performance prediction when algorithms are implemented on commercially available parallel machines. This is mainly because these models do not provide a reasonable scheme for measuring the communication overhead. Recently several practical parallel models aiming at achieving portability and scalability of parallel algorithms have been widely discussed. Among them, the Bulk Synchronous Parallel (BSP) model has received much attention as a bridging model for parallel computation, as it generally better addresses practical concerns like communication and synchronization. The BSP model has been used in a number of application areas, primarily in scientific computing. Yet, very little work has been done on problems generally considered to be irregularly structured, which usually result in highly data-dependent communication patterns and make it difficult to achieve communication efficiency. Typical examples are fundamental problems in graph theory and computational geometry, which are important as a vast number of interesting problems in many fields are defined in terms of them. Thus practical and communication-efficient parallel algorithms for solving these problems are important. In this dissertation, we present scalable parallel algorithms for some fundamental problems in graph theory and computational geometry. In addition to the time complexity analysis, we also present some techniques for worst-case and average-case communication complexity analyses. Experimental studies have been performed on two different architectures in order to demonstrate the practical relevance. Thu, 02 Aug 2001 14:52:25 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-07.prn %A LUO, Hui %T KNOWLEDGE-BASED IMAGE UNDERSTANDING AND CLASSIFICATION SYSTEM FOR MEDICAL IMAGE DATABASES %R 2001-07 %D July 30, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Medical images databases, Knowledge-based, image understanding, image classification, feature extraction, snake model, object-oriented representation %X The understanding of medical images involves the identification of anatomical structures in images, the establishment of the relationships among the structures and the matching them with pre-defined anatomical models. The closer this match, the better the image is understood. Hence, the development and use of anatomical knowledge models are critical to the effectiveness of the system. In this thesis, we will present a new knowledge model for medical image content analysis based on the object-oriented paradigm. The new model abstracts common properties from different types of medical images by using three attributes: description, component, and semantic graph, and specifies its actions to schedule the detection procedure, properly deform the model shapes to match the corresponding anatomies in images, select the best match candidates, and verify the candidates”Æ spatial relations with the semantic graph defined in the model. The advantage of the new model includes: 1) It presents a robust representation ability to represent the object variability, 2) It provides a tighter bond between features and methods, and 3) It supports the complex image analysis and works on both normal and abnormal images. Based on this model, a knowledge-based medical image classification system is developed. The system assigns each input image with one or more most similar models by performing a two-stage processing. The first stage, coarse shape classification, focuses on the global shape features of objects in the processed images. The second stage performs a detail matching between extracted image features and model specified properties. The output match results imply a set of models which are most possible to be existed in the processed image. To further confirm them, an evaluation strategy is used to reject those unreasonable results and inference the high confidence match models. To improve the detection accuracy, we also proposed a new region model which combines both region and edge information into image segmentation, and reformulate the traditional snake model and level set model with it. As expected, the reformulated models demonstrate robust ability to deal with the ambiguity in images and overcome the problem associated with the initialization. The performance of the system has been tested on different types of digital radiographs, including chest, pelvis, ankle, elbow and etc. The experimental results suggest that the system prototype is applicable and robust, and the accuracy of the system is nearly 70% in our image databases. Thu, 02 Aug 2001 14:58:55 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-08.ps %A Ismail, Haythem O. %A Shapiro, Stuart C. %T The Cognitive Clock: A Formal Investigation of the Epistemology of Time %R 2001-08 %D August 14, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Temporal reasoning, cognitive robotics, knowledge representation %Y I.2.4 %X We present a formal model of time and time perception. The model is used to endow a cognitive agent with a personal sense of time. A personal sense of time is based on a representation of the real-time present that allows the agent to distinguish it from the past and the future, and is continuously changing to reflect the progression of time. This is important for reasoning about, and acting in, dynamic domains and for interacting with other agents (humans, for example). An agent that interleaves reasoning and acting while maintaining a sense of the present faces what has been dubbed {\em the problem of the fleeting now}. A solution to the problem involves, not only endowing the agent with a sense of temporal progression, but also with a feel for how much time has passed. In this paper, we construct a theory of time that allows just that. Mon, 20 Aug 2001 18:14:24 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-09.tr.pdf %A Rapaport, William J. %T Holism, Conceptual-Role Semantics, and Syntactic Semantics %R 2001-09 %D August 17, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K philosophy of artificial intelligence, cognitive science, SNePS, holism, semantics, knowledge representation %X This essay continues my investigation of "syntactic semantics": the theory that, *pace* Searle's Chinese-Room Argument, syntax *does* suffice for semantics (in particular, for the semantics needed for a computational cognitive theory of natural-language understanding). Here, I argue that syntactic semantics (which is internal and first-person) is what has been called a conceptual-role semantics: The meaning of any expression is the role that it plays in the complete system of expressions. Such a "narrow", conceptual-role semantics is the appropriate sort of semantics to account (from an "internal", or first-person perspective) for how a cognitive agent understands language. Some have argued for the primacy of external, or "wide", semantics, while others have argued for a two-factor analysis. But, although two factors can be specified---one internal and first-person, the other only specifiable in an external, third-person way---only the internal, first-person one is needed for understanding how someone understands. A truth-conditional semantics can still be provided, but only from a third-person perspective. Mon, 20 Aug 2001 18:18:53 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-10.ps %A Pavan, A. %T Average-case complexity theory and polynomial-time reductions %R 2001-10 %D August 26, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K average-case complexity, reasonable distributions, distributionally-hard languages, polynomial-time reducibilities, separating NP-completeness notions %X This thesis studies average-case complexity theory and polynomial-time reducibilities. The issues in average-case complexity arise primarily from Cai and Selman's extension of Levin's definition of average polynomial time. We study polynomial-time reductions between distributional problems. Under strong but reasonable hypotheses we separate ordinary $\NP$-completeness notions. The average-case complexity of a problem is, in many cases, a more significant measure than the worst-case complexity. It is known that some $\NP$-complete problems, such as $k$-coloring and Hamiltonian cycle, can be solved quickly on average. This has motivated the development of the study of average-case analysis of algorithms. Levin~\cite{Levin86} initiated a general study of average-case complexity by defining a robust notion of average polynomial time and the notion of distributional $\NP$-completeness. Cai and Selman ~\cite{CaiSelman99} gave a general definition of {\em $T$ on aver age} for arbitrary time bounds $T$. They observed difficulties with Levin's definition of average polynomial time when applied to unreasonable input distributions. Their definition of average polynomial time slightly modifies Levin's definition to avoid these difficulties. In this thesis we study reasonable distributions, distributionally-hard languages, and reductions among distributional problems. We prove several results demonstrating that it suffices to restrict one's attention to reasonable distributions. This is important because both Levin's definition and Cai and Selman's definition yield unsatisfactory consequences when we permit unreasonable distributions. We show that if $\NP$ has a $\DTIME(2^n)$-bi-immune language, then every $\DistNP$-complete problem must have a reasonable distribution. We prove that the class $\ppcomp$, the set of languages that can be decided in average polynomial time with respect to every polynomial-time computable distribution, remains unchanged when restricted to reasonable distributions. We strengthen and present a simpler proof of a result of Belanger and Wang~\cite{BelangerWang96}, which shows that Cai and Selm an's definition of average-polynomial time is not closed under many-one reductions. Cai and Selman showed that every is $\P$-bi-immune language is dis\-tri\-bu\-tionally-hard. We study the question of whether there exist distributionally-hard languages that are not $\P$-bi-immune. First we show that such languages exist if and only if $\P$ contains $\P$-printable-immune sets. Then we extend this characterization significantly to include assertions about several traditional questions about immunity, about finding witnesses for $\NP$-machines, and about the existence of one-way functions. Next we study polynomial-time reducibilities. Ladner, Lynch, and Selman~\cite{LadnerLynchSelman75} showed, in the context of worst-case complexity, that various poly\-no\-mi\-al-t ime reductions differ in $\E$. We show similar results for reductions between distributional problems and we show that most of the completeness notions for $\DistEXP$ are different. Finally, we turn our attention to the question of whether various notions of $\NP$-completeness are different. Lutz and Mayordomo, under the hypothesis that the $p$-measure of $\NP$ is not zero, and Ambos-Spies and Bentzien, under the hypothesis that $\NP$ has a $p$-generic language, showed that various completeness notions in $\NP$ are different. We introduce a structural hypothesis not involving stochastic properties and prove that the existence of a Turing complete language for $\NP$ that is not truth-table complete follows from our hypothesis. This result is the first to provide evidence that truth-table completeness for $\NP$ is weaker than Turing completeness for $\NP$. Tue, 28 Aug 2001 17:20:27 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-11.ps %A Ismail, Haythem O. %T Reasoning and Acting in Time %R 2001-11 %D August 24, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Knowledge representation, cognitive robotics, temporal reasoning %Y I.2.4 %X This dissertation investigates aspects of the design of an embodied cognitive agent that interleaves reasoning, acting, and interacting with other agents while maintaining a record of what has happened and is happening in its environment. Among other things, such knowledge of its own history allows the agent to reason more effectively when faced with an emergency situation such as the failure of one of its acts. Crucial to distinguishing what has happened from what is happening is a notion of the present time, or ``now''. There has been much research in artificial intelligence on issues of time. However, it is typically the case that, although an agent reasons about time, it is not itself situated {\em in} time. Once the agent has a concept of ``now'', one that continuously changes to reflect the progression of time, a different kind of temporal reasoning problem emerges. For example, given that an agent could be told anything, how are formal representations of present states to be distinguished from those of past states, where the former, but not the latter, are pertinent to the agent's actions? And, given that the present must be distinguished, how is ``now'' to be modeled so that the mere passage of time does not result in computationally costly knowledge-base-editing routines? How can the agent reason about ``now'', when the very process of reasoning results in ``now'' changing? How can the agent be endowed with a feel for how much time has passed, which seems crucial for reasoning about persistence as time passes while the agent acts? In this dissertation, the above issues are investigated in detail. A theory of subjective time is presented, accounting for a cognitive agent's {\em vague} concept of ``now'', its sense of temporal progression, and its feel for how much time has passed. An investigation of the impact of embodiment and time perception on issues of reasoning about persistence as the agent acts comes out as a natural by-product of the theory. The theory of subjective time is wrapped around a core logic of objective time that axiomatizes various aspectual phenomena needed for reasoning, acting, and natural language interaction. Unlike most theories of linguistic aspect, the logic of aspect presented here accounts for the agent's knowledge of states, events, and processes, not only from static natural language inputs, but also from the dynamic accumulation of perceptual and proprioceptual information as events unfold in time. Based on the logical analysis of the notion of telicity (the analysis goes beyond the standard telic/atelic distinction), a theory of how cognitive agents may employ reasoning to control the execution of sequences of acts is presented. The theory proposes a principled way by which agents may decide when it is time to move on to the next step in a sequence; an issue that has not been given much attention in the literature. Finally, the dissertation establishes a framework for interrupt-handling and error recovery based on a system of context-sensitive priorities among acts. Wed, 29 Aug 2001 17:12:17 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-12.pdf %A Song, Yuqing andhang, Aidong %T Monotonic Tree of Images and Its Application in Image Processing %R 2001-12 %D August 29, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Image retrieval %Y Image processing %X Contour trees have been used in geographic information systems (GIS) and medical imaging to display scalar data. Contours are only defined for continuous functions. For an image represented by discrete data, a continuous function is first defined as an interpolation of the data. Then the contour tree is defined on this continuous function. In this paper, we introduce a new concept termed monotonic line, which is directly defined on discrete data. All monotonic lines in an image form a tree, called monotonic tree. As compared with contour trees, monotonic trees avoid the step of interpolation, thus can be computed more efficiently. Monotonic tree can be reduced. The reduced monotonic tree can also be used as a hierarchical representation of image structures in image processing. In particular, we demonstrate its application on image smoothing and texture retrieval. Experiments show that our smoothing scheme is successful in both noise reduction and texture retrieval. Tue, 04 Sep 2001 14:36:20 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-13.pdf %A Qiao, Chunming %A Xu, Dahai %T Distributed Partial Information Management (DPIM) Schemes for Survivable Networks - Part I %R 2001-13 %D July 10, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K distributed routing and signaling, bandwidth guarantee, sharing, allocation and deallocation,protection %Y Algorithms %X This paper describes a novel framework, called Distributed Partial Information Management (or DPIM). It addresses several major challenges in achieving efficient shared path protection under distributed control with only partial information, including (1) how much partial information about existing active and backup paths (or APs and BPs respectively) is maintained and exchanged; (2) how to obtain a good estimate of the bandwidth needed by a candidate BP, called BBW, and subsequently select a pair of AP and BP for a connection establishment request so as to minimize total bandwidth consumption and/or maximize revenues; (3) how to distributively allocate minimal BBW (and de-allocate maximal BBW) via distributed signaling; and (4) how to update and subsequently exchange the partial information. A DPIM-based scheme using Integer Linear Programming is described to illustrate our approach. In addition, an ultra-fast and efficient heuristic scheme is described. With about the same amount of partial information, such a heuristic-based DPIM scheme can achieve almost as a good performance as the ILP-based DPIM scheme, and a much better performance than another ILP-based scheme described in [1]. The paper also presents an elegant method to support dynamic requests for protected, unprotected, and pre-emptable connections in the unified DPIM framework. Tue, 02 Oct 2001 01:22:13 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-14.pdf %A Xu, Dahai %A Qiao, Chunming %T Distributed Partial Information Management (DPIM) Schemes for Survivable Networks - Part II %R 2001-14 %D July 10, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K bandwidth sharing, distributed routing, on-line heuristic, potential cost %Y Algorithms %X A major challenge in shared path protection is to select a jointly optimized pair of active and backup paths. While Integer Linear Programming (ILP) based approaches are notoriously time consuming, existing heuristics such as active path first (APF) can only achieve sub-optimal results. In this paper, we propose a novel heuristic called APF with potential backup cost or APF-PBC under the distributed partial information management framework described in [1] for ultra-fast processing of on-line requests. We show that APF-PBC can outperform existing schemes based on Integer Linear Programming (ILP) with exactly the same input (either partial or complete information) and constraint. We also show how an intuitive function to compute the potential backup cost is derived mathematically based on the statistical analysis of experimental data. Tue, 02 Oct 2001 01:23:49 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-15.ps %A Jayaraman, B. %A Tambay, P. %T Semantics and Applications of Constrained Objects %R 2001-15 %D October 12, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Constrained objects, Modeling, Object-oriented, Constraint Logic Programming, Semantics %Y Languages %X This paper describes a compositional approach to modeling complex systems. The building block, called a constrained object, is an object whose internal state is governed by a set of (declarative) constraints. Especially in the engineering domain, a constrained object models in a natural manner the internal state and invariants of an engineering artifact, e.g., a resistor in a circuit, a joint in a truss, a gear in a gear box, a heat exchanger in a chemical process plant, etc. When several constrained objects are aggregated to form a complex object, their internal states might further have to satisfy interface constraints. The resulting behavior of the system is obtained by a process of logical inference and constraint satisfaction. Our work extends previous research by providing a richer modeling language, with quantified and conditional constraints, as well as preferences. We show that the paradigm of constrained objects is superior to both a pure object-oriented language as well as a pure constraint language. We present several examples in this paper, and also describe the formal declarative and operational semantics of our language. The declarative semantics for constrained objects is given in terms of a set-theoetic approach, and the operational semantics makes use of top-down goal reduction, constraint solving, and pruning according to preferences. Wed, 21 Nov 2001 14:48:59 GMT %U http://www.cse.buffalo.edu/tech-reports/2001-16.ps %A Mahapatra, Nihar R. %A Dutt, Shantanu %T An Efficient Delay-Optimal Distributed Termination Detection Algorithm %R 2001-16 %D November 27, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K Broadcast, detection delay, distributed computation, k-ary n-cubes, message complexity, message passing, termination detection. %Y F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY %X One of the important issues to be addressed when solving problems on parallel machines or distributed systems is that of efficient termination detection. Numerous schemes with different performance characteristics have been proposed in the past for this purpose. These schemes, while being efficient with regard to one performance metric, prove to be inefficient in terms of other metrics. A significant drawback shared by all previous methods is that they may take as long as $\Theta(P)$ time to detect and signal termination after its actual occurrence, where $P$ is the total number of processing elements. Detection delay is arguably the most important metric to optimize, since it is directly related to the amount of idling of computing resources and to the delay in the utilization of results of the underlying computation. In this paper, we present a novel termination detection algorithm that is simultaneously optimal or near-optimal with respect to all relevant performance measures on any topology. In particular, our algorithm has a best-case detection delay of $\Theta(1)$ and a finite optimal worst-case detection delay on any topology equal in order terms to the time for an optimal one-to-all broadcast on that topology---we derive a general expression for an optimal one-to-all broadcast on an arbitrary topology, which is an interesting new result in itself. On $k$-ary $n$-cube tori and meshes, the worst-case delay is $\Theta(D)$, where $D$ is the diameter of the architecture. Further, our algorithm has message and computational complexities of $O(\max(MD,P))$ ($\Theta(\max(M,P))$ on the average for most applications---the same as other message-efficient algorithms) and an optimal space complexity of $\Theta(P)$, where $M$ is the total number of messages used by the underlying computation. We also give a scheme using counters that greatly reduces the constant associated with the average message and computational complexities, but does not suffer from the counter-overflow problems of other schemes. Finally, unlike some previous schemes, our algorithm does not rely on FIFO ordering for message communication to work correctly. Wed, 05 Dec 2001 15:41:47 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-01.ps %A Anand, Vishal %A Chauhan, Sunit %A Qiao, Chunming. %T Sub-path Protection: A New Framework for Optical Layer Survivability and its Quantitative Evaluation %R 2002-01 %D January 02, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K WDM networks, lightpath, wavelength routing, wavelength assignment, protection, restoration, path protection, link protection, sub-path protection, time to recover. %X In wavelength division multiplexed networks (WDM) with 1:1 path protection, a link-disjoint protection (backup) path is also set up at the time of setting up a working (primary) path. Hence, the failure of a single fiber-link does not cause huge data losses. Typically, past research has considered two survivability paradigms: (a) path protection/restoration and (b) link protection/restoration. In path based schemes a backup path (which is link-disjoint with the primary path) and wavelength is reserved during primary path setup, while in link based schemes, for every link along the primary path a link disjoint backup for that link is found and reserved. Each of these schemes have their advanatges and disadvantages in terms of capacity utilization and restoration times. In our study here, we introduce a new protection/restoration scheme called Sub-path protection. We show that this scheme has advantages over the traditional link and path based schemes. Also sub-path based schemes have the added advantge that they can survive multiple-link failures. Experimental results show that sub-path protection has interesting trade-off in terms of capacity utilization and recovery times. A network provider can take advantage of such a scheme to optimize his network carrying capacity and survivability. Wed, 02 Jan 2002 16:09:56 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-02.ps %A Ngo, Hung Q. %T P-Species and the q-Mehler Formula %R 2002-02 %D January 24, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K bijective proof, q-Mehler formula, species, Kibble-Slepian formula %X In this paper, we present a bijective proof of the $q$-Mehler formula. The proof is in the same style as Foata's proof of the Mehler formula. Since Foata's proof was extended to show the Kibble-Slepian formula, a very general multilinear extension of the Mehler formula, we hope that the proof provided in this paper helps find some multilinear extension of the $q$-Mehler formula. The basic idea to obtain this proof comes from generalizing a result by Gessel. The generalization leads to the notion of species on permutations and the $q$-generating series for these species. The bijective proof is then obtained by applying this new exponential formula to a certain type of species on permutations and a weight preserving bijection relating this species to the $q$-Mehler formula. Some by-products of the $q$-exponential formula shall also be derived. Thu, 24 Jan 2002 19:00:36 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-03.ps %A Burhans, Debra T. %T A Question Answering Interpretation of Resolution Refutation %R 2002-03 %D January 31, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K theorem proving, question answering %X Early use of theorem provers for question answering identified the presence of an answer with the presence of a proof. Later work recognized other types of answers whose existence was not associated with proof, including intensional and conditional answers. This work is concerned with the problem of defining what is meant by answer in the context of resolution theorem proving. Clauses that are relevant are all identified as answers, where relevance is determined with respect to a question and knowledge base: any clause descended from the negated question is deemed relevant. This definition of relevance is not in and of itself novel; rather, it is the way in which the set of relevant clauses is partitioned that provides the key to interpreting clauses as answers. A partition that divides the set of relevant clauses into three classes, termed specific, generic, and hypothetical, is proposed. These classes are formally distinguished by the way in which literals in a clause share variables, with class membership based on a property termed the closure of variable sharing of a literal. The best answers are identified with relevant clauses that are, additionally, informative. The informativeness of a clause is determined with respect to a set of clauses termed the answer set, where an informative clause contains information not conveyed by any other clause in the set. The process of reasoning in search of a proof is recast as the process of constructing a sequence of answer sets, starting with the empty set, where each set in the sequence is at least as informative as the previous set. It is this property that identifies question answering as an anytime reasoning process. The complete answer set for a given question and knowledge base is shown to be the fixed point of the answer set generation function. While this potentially infinite set may never be realized by a reasoner, the current answer set is guaranteed to contain the most informative, relevant clauses available at any point during reasoning. Different control structures give rise to different answer set sequences, and may be selectively employed to generate preferred answers as quickly as possible. The definition of answer sets elucidates the importance of separating answer search from answer selection, and highlights the subjectivity of the notion of best answer as defined in many question answering systems. The complete characterization of resolvents as answers presented herein provides a framework that accounts for and expands upon previous work on question answering in a resolution theorem prover. In addition, it provides a foundation for further work in question answering by establishing a context-independent logical pragmatics of question answering. Thu, 07 Feb 2002 13:46:31 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-04.ps %A Garg, Ashim %A Rusu, Adrian %T Straight-line Drawings of Binary Trees with Linear Area and Good Aspect Ratio %R 2002-04 %D April 24, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K tree drawing straight-line grid planar aspect ratio area %X Trees are usually drawn planar, i.e. without any crossings.In this paper, we investigate the area requirement of (non-upward) planar straight-line drawings of binary trees. Let $T$ be a binary tree with $n$ vertices. We show that $T$ admits a planar straight-line grid drawing with area O(n) and with any prespecified aspect ratio in the range [1,n^\alpha], where \alpha is a constant such that 0 <= \alpha < 1. We also show that such a drawing can be constructed in O(nlog n) time. Wed, 24 Apr 2002 19:34:51 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-05.ps %A Garg, Ashim %A Chanda, Amrita %T Compact Encodings of Planar Orthogonal Drawings %R 2002-05 %D April 24, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K encoding graph drawing orthogonal planar %X We present time-efficient algorithms for encoding (and decoding) planar orthogonal drawings of degree-4 and degree-3 biconnected and triconnected planar graphs using small number of bits. We also present time-efficient algorithms for encoding (and decoding) turn-monotone planar orthogonal drawings. Wed, 24 Apr 2002 19:34:55 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-08.pdf %A Wu, Hongyi %T iCAR : an Integrated Cellular and Ad hoc Relaying System %R 2002-08 %D May 16, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K iCAR, cellular, ad hoc, wireless, mobile, network, integrated %X The cellular concept was introduced for wireless communication to address the problem of having scarce frequency resource. It is based on the sub-division of geographical area to be covered by the network into a number of smaller areas called cells. Frequency reuse in the cells far away from each other increases system's capacity. But at the same time, the cell boundaries prevent the channel resource of a system to be fully available for users. No access to Data Channels (or DCHs) in other cell by the mobile host (or MH) limits the channel efficiency and consequently the system capacity. In this dissertation, we propose a new wireless system architecture based on the integration of cellular and modern ad hoc relaying technologies, called iCAR. It can efficiently balance traffic loads and share channel resource between cells by using Ad hoc relaying stations (ARSs) to relay traffic from one cell to another dynamically. This not only increases the system's capacity cost-effectively, but also reduces transmission power for mobile hosts and extends system coverage. We analyze the system performance in terms of the call blocking probability and queuing delay using multi-dimensional Markov chains for the new call requests and the call dropping probability for handoff requests, and verify the analytical results via simulations. Our results show that with a limited number of ARSs and some increase in the signaling overhead (as well as hardware complexity), the call blocking/dropping probability in a congested cell as well as the overall system can be reduced. We also propose a seed-growing approach for ARS placement, and discuss the upper bound on the number of seed ARSs needed in the system. In order to quantitatively evaluate ARS placement strategies, we introduce the concept of a new performance metric called quality of (ARS) coverage (QoC) for the comparison of various ARS placement strategies, and propose three rules of thumb as guidelines for cost-effective ARS placement in iCAR. Furthermore, we propose the signaling and routing protocols for establishing QoS guaranteed connections for IP traffic in iCAR. In particular, we discuss how a relaying route between a MH and a BTS in a nearby cell can be established via ARSs, and evaluate the performance of the protocols in terms of request rejection rate and signaling overhead through simulations. In addition, we propose a novel concept called ``managed mobility" and address the ARS mobility management in iCAR. Fri, 17 May 2002 14:51:59 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-07.ps %A Ngo, Hung Q. %A Vu, Van H. %T On Multi-rate Rearrangeable Clos Networks and a Generalized Edge Coloring Problem on Bipartite Graphs %R 2002-07 %D May 10, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K Multirate Rearrangeability, Clos Networks, Bipartite Graph Edge Coloring %X Chung and Ross (SIAM J. Comput., \textbf{20}, 1991) conjectured that the minimum number $m(n,r)$ of middle-state switches for the symmetric $3$-stage Clos network $C(n,m(n,r),r)$ to be rearrangeable in the multirate enviroment is at most $2n-1$. This problem is equivalent to a generalized version of the bipartite graph edge coloring problem. The best bounds known so far on this function $m(n,r)$ is $11n/9 \leq m(n,r) \leq 41n/16 + O(1)$, for $n, r \geq 2$, derived by Du-Gao-Hwang-Kim (SIAM J. Comput., \textbf{28}, 1999). In this paper, we make several contributions. Firstly, we give evidence to show that even a stronger result might hold. In particular, we show that $m(n,r) \leq \lceil (r+1)n/2 \rceil$, which implies $m(n,2) \leq \lceil 3n/2 \rceil$ - stronger than the conjectured value of $2n-1$. Secondly, we derive that $m(2,r) = 3$ by an elegant argument. Lastly, we improve both the best upper and lower bounds given above: $\lceil 5n/4 \rceil \leq m(n,r) \leq 2n-1+\lceil (r-1)/2 \rceil$, where the upper bound is an improvement over $41n/16$ when $r$ is relatively small compared to $n$. We also conjecture that $m(n,r) \leq \lfloor 2n(1-1/2^r) \rfloor$. Fri, 24 May 2002 17:54:44 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-09.ps %A Ngo, Hung Q. %T A New Routing Algorithm for Multirate Rearrangeable Clos Networks %R 2002-09 %D May 22, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K Multirate rearrangeability, Clos Networks, Routing Algorithms %X In this paper, we study the problem of finding routing algorithms on the multirate rearrangeable Clos networks which use as few number of middle-stage switches as possible. We propose a new routing algorithm called the ``grouping algorithm''. This is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. In particular, the grouping algorithm implies that $m=2n+\lceil\frac{n-1}{2^k}\rceil$ is a sufficient number of middle-stage switches for the symmetric $3$-stage Clos network $C(n,m,r)$ to be multirate rearrangeable, where $k$ is any positive integer and $r \leq n/(2^k-1)$. Fri, 24 May 2002 17:55:57 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-10.ps %A Ngo, Hung Q. %T WDM Split Cross-connects and $3$-stage Clos Networks %R 2002-10 %D July 09, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K WDM split cross-connects, Clos Networks, Routing Algorithms %X In this paper, we first show that a wavelength division multiplexed (WDM) split cross-connect is strictly, wide-sense, or rearrangeably non-blocking if and only if a corresponding $3$-stage Clos network is strictly, wide-sense or rearrangeably non-blocking. This observation implies known results on strictly non-blocking WDM split cross-connects and gives rise to new results on wide-sense and rearrangeably non-blocking WDM split cross-connects. We next introduce a routing algorithm for the Clos networks which show that there are wide-sense non-blocking Clos networks which are not strictly non-blocking. Hence, the same holds for the WDM split cross-connects. We also consider another demand model for WDM split cross-connects and present associated results. Routing algorithms for WDM split cross-connects could be viewed as on-line and off-line algorithms to edge-color a class of bipartite multi-graphs. Tue, 16 Jul 2002 12:56:43 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-11.pdf %A Anand, Vishal %A Qiao, Chunming %T Effect of Wavelength Conversion in Survivable Wavelength Routed Optical WDM Networks with Alternate Routing %R 2002-11 %D June 06, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K Optical network, Wavelength Division Multiplexing (WDM), Routing and Wavelength assignment (RWA), all-optical networks, wavelength conversion, network survivability, Traffic models, network blocking, alternate routing. %X This study focuses on the routing and wavelength assignment in wavelength-routed optical wavelength-divisioned -multiplexed networks with circuit switching using wavelength conversion. Wavelength conversion has been proposed for use in such networks to improve the efficiency. The crucial factors which determine the efficiency of using wavelength conversion as opposed to not using them, is the number of wavelengths required to satisfy the network traffic demand and the blocking of traffic demands by the network. In addition to considering wavelength conversion, this study investigates the effect of having multiple paths between each source-destination pair. We consider the cases where protection is necessary for each of the primary paths between every source-destination pair and hence a backup path also has to be established during connection set up, and the case when no protection is necessary. We study the effect of wavelength conversion with different protection schemes. By simulating and analyzing a large number of randomly generated networks we report results of our study of the above schemes under both incremental and dynamic traffic conditions. The study shows that utilizing wavelength conversion has a considerable impact on reducing network blocking under both incremental and dynamic traffic conditions, on the other hand we find the difference in wavelength requirements of the various schemes considered is minimal. Wed, 07 Aug 2002 18:19:38 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-12.ps %A Song, Yuqing %T MONOTONIC TREE AND ITS APPLICATION TO MULTIMEDIA INFORMATION RETRIEVAL %R 2002-12 %D August 16, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K monotonic tree, information retrieval, image retrieval, semantics %X Contour trees have been used in geographic information systems (GIS) and computer imag-ing to display scalar data. Contours are only defined for continuous functions. For discrete data, a continuous function is first defined as an interpolation of the data. Then a con-tour tree is defined on this continuous function. In this dissertation, we first introduce a new concept termed monotonic line, which models contour lines of discrete functions. All monotonic lines in a discrete function form a tree, called monotonic tree. As compared with contour trees, monotonic trees avoid the step of interpolation, thus can be computed and manipulated more efficiently. In addition, when used in image processing, monotonic trees retrieve similar structures as contour trees do while reserving the discreteness of image data. In computer imaging, the discreteness of image data is one main factor which makes image processing and understanding so difficult. The discreteness of image data itself is a research topic. Monotonic trees are used as a hierarchical representation of image structures in content-based multimedia retrieval. Although a variety of techniques have been developed for content-based image retrieval (CBIR), automatic image retrieval by semantics still remains a challenging problem due to the difficulty in object recognition and image understand- ing. In this dissertation, we present a novel approach to support semantics-based image retrieval on the basis of monotonic trees. The structural elements of an image are modeled as branches (or subtrees) of the monotonic tree. These elements are classified and clustered on the basis of such properties as color, spatial location, coarseness, and shape. Each cluster corresponds to some semantic feature. Following these steps, images can be automatically annotated with category keywords. So high-level (semantics-based) querying and brows-ing of images can be supported. This scheme is applied to retrieve scenery features from images and locate smooth background in images. Comparisons of experimental results of this approach with conventional techniques using low-level features demonstrate the effec-tiveness of our approach. In future work, the monotonic tree model will be extended to general semantic categories on both images and videos. This dissertation has two main contributions. The first contribution is the mathematical theory of monotonic tree, which is the first theory addressing definitions, properties, and computations of contour structures directly on discrete functions. The second contribution is the application of monotonic tree model to semantics-based image retrieval. The success of this model on scenery features and smooth background implies its potential in analyzing general semantics of both images and videos. Tue, 20 Aug 2002 13:57:34 GMT %U http://www.cse.buffalo.edu/tech-reports/90-21.ps %A Shapiro, Stuart C. %A Rapaport, William J. %T The SNePS Family %R 90-21 %D September 1, 1990 %I Department of Computer Science and Engineering, SUNY Buffalo %K SNePS, semantic networks %Y I.2 ARTIFICIAL INTELLIGENCE I.2.0 General-Cognitive simulation I.2.0 General-Philosophical foundations I.2.1 Applications and Expert Systems (see also H.4,J)-Natural language interfaces I.2.3 Deduction and Theorem Proving-Deduction (e.g., natural, rule-based) I.2.3 Deduction and Theorem Proving-Nonmonotonic reasoning and belief revision I.2.4 Knowledge Representation Formalisms and Methods I.2.4 Knowledge Representation Formalisms and Methods-Representation languages I.2.4 Knowledge Representation Formalisms and Methods-Semantic networks %X SNePS, the Semantic Network Processing System, has been designed to be a system for representing the beliefs of a natural language using intelligent system (a ``cognitive agent''). It has always been the intention that a SNePS-based ``knowledge base'' would ultimately be built, not by a programmer or knowledge engineer entering representations of knowledge in some formal language or data entry system, but by a human informing it using a natural language (generally supposed to be English), or by the system reading books or articles that had been prepared for human readers. This document describes the history of SNePS and some recent SNePS projects. It has been superseded by: Shapiro, Stuart C., & Rapaport, William J. (1992), ``The SNePS Family,'' _Computers and Mathematics with Applications_, Vol. 23: 243-275. Reprinted in Fritz Lehmann (ed.), _Semantic Networks in Artificial Intelligence_ (Oxford: Pergamon Press, 1992): 243-275. Mon, 09 Sep 2002 12:52:04 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-15.pdf %A "Aygun, Ramazan Savas %A Zhang, Aidong" %T Rule-based Flexible Synchronization Modeling with Model Checking %R 2002-15 %D December 05, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K Multimedia Synchronization, Model Checking, Synchronization Rules, Multimedia Presentations, Linear Temporal Logic. %X Specification as in SMIL usually considers forward presentation without considering interactions that change the course of the presentation like backward and skip. Also, management of the presentation constraints become harder when the course of the presentation changes. In this report, we introduce a synchronization model, termed RuleSync, for management of robust, consistent, and flexible presentations that include a comprehensive set of interactions. RuleSync manipulates synchronization rules that are managed by Receiver-Controller-Actor (RCA) scheme where receivers, controllers and actors are objects to receive events, to check conditions and to execute actions, respectively. The correctness of the model and the presentation is controlled with a technique called {\it model checking}. Model checker PROMELA/SPIN tool is used for automatic verification of the correctness of LTL (Linear Temporal Logic) formulas. %Z Thu, 05 Dec 2002 19:43:22 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-16.pdf %A Aygun, Ramazan Savas %A Yazici, Adnan %T Modeling and Management of Fuzzy Information in Multimedia Database Applications %R 2002-16 %D December 05, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K Multimedia Databases, Object-Oriented Data Model, ExIFO2,FOOD, Fuzziness, Uncertainty %X In this report, we firstly present a conceptual data model for multimedia database applications based on ExIFO2 model. The ExIFO2 data model is chosen as the conceptual model since it handles complex objects along with their uncertain and imprecise properties. We enhanced this conceptual model in order to meet the multimedia data requirements. In addition to uncertain and imprecise information, we present a way of handling relationships among objects of multimedia database applications. Events that might be extracted from video or audio are also considered in this study. Secondly, the conceptual model is mapped to a logical model, which the fuzzy object-oriented data (FOOD) model is chosen, for storing and manipulating the multimedia objects. This mapping is done in a way that it preserves most of the information represented at the conceptual level. Finally, in this study videos of football (soccer) games is selected as the multimedia database application to show how we handle crisp and fuzzy querying and retrieval of fuzzy and crisp data from the database. %Z Thu, 05 Dec 2002 19:43:24 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-17.ps %A Boxer, Laurence %T Expected Optimal Selection on the PRAM %R 2002-17 %D December 03, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K parallel algorithm, selection, parallel random access machine (PRAM), expected value, variance, Chebyshev's Inequality %Y F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY %X The Selection Problem is the following: Given a totally ordered set $S$ of $n$ items and an integer $k$ such that $0 < k \leq n$, find the $k$-th smallest member of $S$. A general algorithm for a PRAM using optimal $\Theta(n)$ cost is not currently known. In this paper, we show that if the input set $S$ is uniformly (randomly) distributed on an interval $[a,b]$, then the Selection Problem may be solved by an algorithm with the following properties: a) The expected cost is an optimal $\Theta(n)$. b) The worst-case cost is $\Theta(n \log^{(2)} n)$, which matches that of the most efficient algorithm in the literature~\cite{JaJa}. %Z Thu, 05 Dec 2002 19:49:32 GMT %U http://www.cse.buffalo.edu/tech-reports/98-08.ps %A Yu, Dantong %A Chatterjee, Surojit %A Sheikholeslami, Gholamhosein %A Zhang, Aidong %T Efficiently Detecting Arbitrary Shaped Clusters in Very Large Datasets with High Dimensions %R 98-08 %D November 1, 1998 %I Department of Computer Science and Engineering, SUNY Buffalo %K Data clustering, hash table, wavelet transform, very large databases %X Multimedia databases typically contain data with very high dimensions. Finding interesting patterns in these databases poses a very challenging problem because of the scalability,lack of domain knowledge and complex structures of the embedded clusters. High dimensionality adds severely to the scalability problem. It has been shown that the wavelet-based clustering technique, WaveCluster, is very efficient and effective in detecting arbitrary shape clusters and eliminating noisy data for low dimensional data. In this paper, we introduce {\it HiperWave}, an approach to applying wavelet-based techniques for clustering high dimensional data. Using a hash-based data structure, our approach makes intelligent use of available resources to discover clusters in the dataset. We demonstrate that the cost of clustering can be reduced dramatically yet maintaining all the advantages of wavelet-based clustering. This hash-based data representation can be applied for any grid-based clustering approaches. Finally, we introduce a quantitative metric to measure the quality of the resulting clusters. The experimental results show both effectiveness and efficiency of our method on high dimensional datasets. %Z Fri, 17 Jan 2003 13:39:30 GMT %U http://www.cse.buffalo.edu/tech-reports/98-07.ps %A Sheikholeslami, Gholamhosein %A Wang, Wenjie %A Zhang, Aidong %T A Model of Image Representation and Indexing in Image Database Systems %R 98-07 %D July 20, 1998 %I Department of Computer Science, SUNY Buffalo %K content-based image retrieval, image decomposition %X Image database systems need to be built to support effective and efficient access to image data on the basis of content. In this process, significant features must first be extracted from image data in their pixel format. These features must then be classified and indexed to assist efficient retrieval of image content. However, the issues central to automatic extraction and indexing of image content remain largely an open problem. In this paper, we investigate effective block-oriented image decomposition structures to be used as a fundamental data model for representing image content in large image databases. A hierarchical structure $S^g$-tree is introduced to decompose database images. Each decomposition of an image segment generates n subsegments of equal-size that are uniformly distributed within the image segment. Our analysis illustrates a special case of S^g-tree, nona-tree decomposition, when n equals 9, is an effective and efficient block-oriented decomposition structure to facilitate content-based image retrieval. Using S^g-tree structure to represent image content in an image database, flexible access to partial contents of each database image can be provided. Various types of content-based queries and efficient image retrieval can then be supported through novel indexing and searching approaches. %Z Fri, 17 Jan 2003 13:40:20 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-01.pdf %A "Tambay P. %A Jayaraman B." %T The Cob Programmer's Manual %R 2003-01 %D February 05, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Constrained Objects, Constraints, Logic Programming, Object-Oriented, Modeling %Y Languages %X Cob is a programming language and execution environment based on the concept of constrained objects for compositional and declarative modeling of engineering structures. A constrained object is an object whose internal state is governed by a set of (declarative) constraints. When several constrained objects are aggregated to form a complex object, their internal states might further have to satisfy interface constraints. The resultant behavior of the complex object is obtained by logical inference and constraint satisfaction. For the domain of engineering modeling, the paradigm of constrained objects is superior to both a pure object-oriented language as well as a pure constraint language. While the concept of an object and its attributes capture the structural aspects of an engineering entity, the concept of constraint captures its behavioral properties. Our current prototype includes tools for authoring constrained-object class diagrams; a compiler that translates class diagrams to CLP(R) code; and domain-specific visual interfaces for building and testing constrained objects. This manual describes version 1.0 of the Cob programming language. %Z Wed, 05 Feb 2003 17:22:05 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-02.ps %A Glasser, Christian %A Selman, Alan L. %A Sengupta, Samik %A Zhang, Liyu %T Disjoint NP-Pairs %R 2003-02 %D February 17, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Disjoint NP-pairs, promise problems, oracles, proof systems, P-separable %X We study the question of whether the class DisNP of disjoint pairs (A, B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets that is NP-hard. We show under reasonable hypotheses that nonsymmetric disjoint NP-pairs exist, which provides additional evidence for the existence of P-inseparable disjoint NP-pairs. We construct an oracle relative to which the class of disjoint NP-pairs does not have a complete pair, an oracle relative to which optimal proof systems exist, hence complete pairs exist, but no pair is NP-hard, and an oracle relative to which complete pairs exist, but optimal proof systems do not exist. %Z Thu, 20 Feb 2003 14:53:04 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-03.pdf %A Wu, Yimin %A Zhang, Aidong %T Adaptively Discovering Meaningful Patterns in High-Dimensional Nearest Neighbor Search %R 2003-03 %D April 08, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %Y Database %X To query high-dimensional databases, similarity search (or k nearest neighbor search) is the most extensively used method. However, since each attribute of high dimensional data records only contains very small amount of information, the distance of two high-dimensional records may not always correctly reflect their similarity. So, a multi-dimensional query may have a k-nearest-neighbor set which only contains few relevant records. To address this issue, we present an adaptive pattern discovery method to search high dimensional data spaces both effectively and efficiently. With our method, the user is allowed to participate in the database search by labeling the returned records as relevant or irrelevant. By using user-labeled data records as training samples, our method employs an adaptive pattern discovery technique to learn the distribution patterns of relevant records in the data space, and drastically reduces irrelevant data records. From the reduced data set, our approach returns the top-k nearest neighbors of the query to the user -- this interaction between the user and the DBMS can be repeated multiple times. To achieve the adaptive pattern discovery, we employ a pattern classification algorithm called random forests, which is a machine learning algorithm with proven good performance on many traditional classification problems.By using a novel two-level resampling method, we adapt the original random forests to an interactive algorithm, which achieves noticeable gains in efficiency over the original algorithm. We empirically compare our method with previously well-known related approaches on large-scaled, high-dimensional and real-world data sets, and report promising results of our method. %Z Wed, 09 Apr 2003 12:12:30 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-04.ps %A Glasser, C. %A Selman, A %A Sengupta, S. %T Reductions between Disjoint NP-Pairs %R 2003-04 %D April 21, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K NP-pairs, reductions, smart reductions, uniformly enumerable, oracle %X We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let $A$, $B$, $C$, and $D$ be nonempty sets belonging to NP. A {\em smart} reduction between the disjoint NP-pairs $(A, B)$ and $(C, D)$ is a Turing reduction with the additional property that if the input belongs to $A \cup B$, then all queries belong to $C \cup D$. We prove under the reasonable assumption $\mathrm{UP} \cap \mathrm{co}\mbox{-}\mathrm{UP}$ has a P-bi-immune set that there exist disjoint NP-pairs $(A, B)$ and $(C, D)$ such that $(A, B)$ is truth-table reducible to $(C, D)$, but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DisjNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair. %Z Tue, 22 Apr 2003 14:44:06 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-05.pdf %A Garg, Ashim %A Rusu, Adrian %T Area-Efficient Order-Preserving Planar Straight-line Drawings of Ordered Trees %R 2003-05 %D May 16, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K graph drawing, order-preserving, straight-line %X Ordered trees are generally drawn using order-preserving planar straight-line grid drawings. We therefore investigate the area-requirements of such drawings, and present several results: Let $T$ be an ordered tree with $n$ nodes. Then: \begin{itemize} \item $T$ admits an order-preserving planar straight-line grid drawing with $O(n\log n)$ area. \item If $T$ is a binary tree, then $T$ admits an order-preserving planar straight-line grid drawing with $O(n\log \log n)$ area. \item If $T$ is a binary tree, then $T$ admits an order-preserving {\em upward} planar straight-line grid drawing with {\em optimal} $O(n\log n)$ area. \end{itemize} We also study the problem of drawing binary trees with user-specified arbitrary aspect ratios. We show that an ordered binary tree $T$ with $n$ nodes admits an order-preserving planar straight-line grid drawing $\Gamma$ with width $O(A+\log n)$, height $O((n/A)\log A)$, and area $O((A+\log n)(n/A)\log A)=O(n\log n)$, where $2\leq A\leq n$ is any user-specified number. Also note that all the drawings mentioned above can be constructed in $O(n)$ time. %Z Fri, 16 May 2003 19:44:36 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-14.pdf %A Garg, Ashim %A Rusu, Adrian %T Straight-line Drawings of General Trees with Linear Area and Arbitrary Aspect Ratio %R 2002-14 %D May 16, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K graph drawing, straight-line, linear area %X Trees are usually drawn planar, i.e. without any crossings. In this paper, we investigate the area requirement of (non-upward) planar straight- line grid drawings of general trees. A {\em degree-d tree} is one in which each node has at most $d$ edges incident on it. Let $T$ be a degree-$d$ tree with $n$ nodes, such that $d =O(n^\delta)$, where $0 \le \delta < 1/2$ is a constant. We show that $T$ admits a planar straight-line grid drawing with area $O(n)$ and with any pre-specified aspect ratio in the range $[n^{-\alpha},n^\alpha]$, where $\alpha$ is a constant such that $0 \leq \alpha < 1$. We also show that such a drawing can be constructed in $O(n\log n)$ time. In particular, our result shows that optimal area (equal to $O(n)$) and optimal aspect ratio (equal to 1) is simultaneously achievable for such drawings. %Z Mon, 19 May 2003 13:33:10 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-06.ps %A "Zhang, Huaming %A He, Xin" %T Canonical Ordering Tree and Its Applications in Graph Drawing %R 2003-06 %D May 30, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K graph, canonical ordering tree, grid embedding, visibility representation %X We study the properties of Schnyder's realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a visibility representation with height at most 15n/16. This improves the previous best bound of (n-1). Second, we show that every plane graph G has a straight-line grid embedding on an (n-\Delta_0-1) \times (n-\Delta_0-1) grid, where \Delta_0 is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n-1) \times (n-1). We also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these properties, we show that every such a graph has a canonical ordering tree with at most (n+1)/2 leaves. This improves the previously known bound of (2n+1)/3. We show that every 4-connected plane graph has a visibility representation with height at most (3n)/4. All drawings discussed in this paper can be obtained in linear time. %Z Tue, 03 Jun 2003 15:02:14 GMT %U http://www.cse.buffalo.edu/tech-reports/2002-13.ps %A Zhang, Huaming %A He, Xin %T On Even Triangulations of 2-Connected Embedded Graphs %R 2002-13 %D July 06, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %X Recently, Hoffmann and Kriegel proved an important combinatorial theorem [HK96]: Every 2-connected bipartite plane graph $G$ has a triangulation in which all vertices have even degree (it's called an even triangulation). Combined with a classical Whitney's Theorem, this result implies that every such a graph has a 3-colorable plane triangulation. Using this theorem, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. A complicated O(n^2) time algorithm was obtained in [HK96] for constructing an even triangulation of G. Hoffmann and Kriegel conjectured that there is an O(n^{3/2}) time algorithm for solving this problem. In this paper, we develop a simple proof of the above theorem. Our proof reveals and relies on a natural correspondence between even triangulations of $G$ and certain orientations of G. Based on this new proof, we obtain a very simple O(n) time algorithm for finding an even triangulation of G. We also extend our proof to show the existence of even triangulations for similar graphs on high genus surface. %Z Tue, 03 Jun 2003 15:23:17 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-07.pdf %A Aygun, Ramazan Savas %T Spatio-Temporal Browsing of Multimedia Presentations %R 2003-07 %D May 08, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Multimedia Presentations, Spatial Browsing, Temporal Browsing, Sprite Generation, Multimedia Synchronization %X Emerging applications like asynchronous distant learning and collaborative engineering require organization of media streams as multimedia presentations. The browsing of presentations enables interactive surfing of the multimedia documents. We propose spatio-temporal browsing of multimedia presentations in the sense that browsing can be performed both in the spatial and temporal domain. The spatial browsing is provided by incorporation of camera controls like panning, tilting, and zooming. Panoramic images enable a kind of browsing by storing the image at high resolutions from various angles. However, the generation of high resolution sprite (mosaic) from digital video is not an easy task. Since the video data may also exist in a compressed format, new features like boundaries have to be extracted from the compressed video. We consider compressed data that is generated by Discrete Cosine Transform (DCT), which has been used in MPEG-1, MPEG-2, MPEG-4, and H263.1. Global Motion Estimation (GME) has been improved for videos where motion does not occur frequently. Motion sensors, which are sensitive pixels to motion, are proposed to indicate the existence of motion and yield quick approximation to the motion. Motion sensors reduce the amount of computations of the hierarchical evaluation of low-pass filtered images in iterative descent methods. The generated sprites are usually more blurred than original frames due to image warping stage and errors in motion estimation. The temporal integration of images is performed using the histemporal filter based on the histogram of values within an interval. The initial frame in the video sequence is registered at a higher resolution to generate high resolution sprite. Instead of warping of each frame, the frames are warped into the sprite at intervals to reduce the blurring in the sprite. We also introduce a new sprite called conservative sprite where new pixels are exclusively mapped on the sprite during temporal integration phase. The sprite pyramid is introduced to handle sprite at different resolutions. To measure the quality of the sprite, a new measure called sharpness is used to estimate the blurring in the sprite. The generated sprite is used for spatial browsing. On the other hand, temporal browsing is closely related with the synchronization of different streams. The power of synchronization models is limited to the synchronization specifications and user interactions. The proposed synchronization model is an event-based model that can handle time-based actions while enabling user interactions like backward and skip. The synchronization model processes the synchronization rules based on Event-Condition-Action (ECA) rules. Since the structure of a synchronization rule is simple, the manipulation of the rules can be performed easily in existence of user interactions. The synchronization model uses Receiver-Controller-Actor (RCA) scheme to execute the rules. In RCA scheme, receivers, controllers, and actors are objects to receive events, to check conditions, and to execute actions, respectively. The synchronization rules can easily be regenerated from SMIL expressions. The deduction of synchronization rules is based on author's specification. A middle layer between the specification and the synchronization model assists the synchronization model to provide user interactions while keeping the synchronization specification minimal. We call this middle layer as middle-tier. The middle-tier for multimedia synchronization handles synchronization rules that can be extracted explicitly from the user specification and synchronization rules that can be deduced implicitly from explicit synchronization rules. The synchronization model also generates a virtual timeline to manage the user interactions that change the course of the presentation. The verification and correctness of schedules are also important. The general methods to check the correctness of a specification are theoretical verification, simulation, and testing. Model checking is a technique that automatically detects all the states that a model can enter and checks the truthness of well-formed formulas. Moreover model checking can present contradictory examples if the formulas are not satisfied. PROMELA/SPIN tool has been used for model checking to check LTL (Linear Temporal Logic) formulas. These formulas can automatically be generated and verified. %Z Tue, 03 Jun 2003 18:27:42 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-08.pdf %A Rusu, Adrian %T Area-Efficient Grid Drawings of Graphs %R 2003-08 %D August 16, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Graph Drawing, Planar, Straight-line, Tree, Outerplanar, Area, Aspect Ratio, Information Visualization, Computational Geometry %Y Algorithms; Theory %X The visualization of relational information is concerned with the presentation of abstract information about relationships between various entities. It has many applications in diverse domains such as software engineering, biology, civil engineering, and cartography. Relational information is typically modeled by an abstract graph, where vertices are entities and edges represent relationships between entities. The aim of graph drawing is to automatically produce drawings of graphs which clearly reflect the inherent relational information. This thesis is primarily concerned with problems related to the automatic generation of area-efficient grid drawings of trees and outerplanar graphs, which are important categories of graphs. The main achievements of this thesis include: \begin{enumerate} \item An algorithm for producing planar straight-line grid drawings of binary trees with optimal linear area and with user-defined arbitrary aspect ratio, \item An algorithm for producing planar straight-line grid drawings of degree-$d$ trees with $n$ nodes, where $d=O(n^{\delta})$ and $0 \le \delta < 1/2$ is a constant, with optimal linear area and with user-defined arbitrary aspect ratio, \item An algorithm which establishes the currently best known upper bound, namely $O(n \log n)$, on the area of order-preserving planar straight-line grid drawings of ordered trees, \item An algorithm which establishes the currently best known upper bound, namely $O(n \log \log n)$, on the area of order-preserving planar straight-line grid drawings of ordered binary trees, \item An algorithm for producing order-preserving upward planar straight-line grid drawings of ordered binary trees with optimal $O(n \log n)$ area, \item An algorithm which establishes the trade-off between the area and aspect ratio of order-preserving planar straight-line grid drawings of ordered binary trees, in the case when the aspect ratio is arbitrarily defined by the user, and \item An algorithm for producing planar straight-line grid drawings of outerplanar graphs with $n$ vertices and degree $d$ in $O(dn^{1.48})$ area. This result shows for the first time that a large category of outerplanar graphs, namely those with degree $d=O(n^{\delta})$, where $0 \le \delta < 0.52$ is a constant, can be drawn in sub- quadratic area. All our algorithms are time-efficient. More specifically, algorithms 1 and 2 run in $O(n \log n)$ time each, and algorithms 3, 4, 5, 6, and 7 run in $O(n)$ time each. %Z Tue, 19 Aug 2003 16:40:25 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-10.pdf %A Zhang, Huaming %A He, Xin %T Improved Visibility Representation of Plane Graphs %R 2003-10 %D August 27, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Graph; Visibility Representation %X In a visibility representation (VR for short) of a plane graph $G$, each vertex of $G$ is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of $G$ are joined by a vertical line segment. Rosenstiehl and Tarjan \cite{RT86}, Tamassia and Tollis \cite{TT86} independently gave linear time VR algorithms for 2-connected plane graph. Using this approach, the height of the VR is bounded by $(n-1)$, the width is bounded by $(2n-5)$. After that, some work have been done to find a more compact VR. Kant and He \cite{KH97} proved that a 4-connected plane graph has a VR with width bounded by $(n-1)$. Kant \cite{Kant97} reduced the width bound to $\lfloor \frac{3n-6}{2} \rfloor$ for general plane graphs. Recently, using a sophisticated greedy algorithm, Lin et. al. reduced the width bound to $\lfloor \frac {22n-42} {15} \rfloor$ \cite{LLS03}. In this paper, we prove that any plane graph $G$ has a VR with width at most $\lfloor \frac {13n-24}{9} \rfloor$, which can be constructed by using the simple standard VR algorithm in \cite{RT86,TT86}. %Z Tue, 02 Sep 2003 18:56:04 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-09.pdf %A Chinchani, Ramkumar %A Pramanik, Suranjan %A Garg, Ashish %T Handling Failures and DOS Attacks Using Network Device Groups %R 2003-09 %D July 15, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Fault tolerant networking; Security %Y Reliability; Security %X With the growing popularity of the Internet and the falling prices of network devices, it is not unusual to find multiple network devices in a computer system. Technologies such as Internet connection sharing and NAT are commonly being used by end users to make network connectivity more viable. In this paper, we point out that this implicit redundancy can be used to achieve fault tolerance. It is known that network devices can be grouped to achieve failover support. However, the focus has been limited to localized factors and device failures. In the context of the Internet, security against DOS attacks also becomes an important issue. While the use of multiple network devices provides a good solution for device failure, it doesn t guarantee a good defense against DOS attacks. We show that computer systems can become tolerant to DOS attacks if some external factors are also taken into account. The main contribution of this paper is a systematic and comprehensive solution that makes a best effort to provide reliable network connectivity even when network device failures and DOS attacks occur. We have implemented and tested this technique in Linux and report our findings. %Z Tue, 02 Sep 2003 19:18:17 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-11.pdf %A Garg, Ashim %A Rusu, Adrian %T Area-Efficient Drawings of Outerplanar Graphs %R 2003-11 %D September 18, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K graph, outerplanar, area, planar, straight-line %X It is well-known that a planar graph with $n$ nodes admits a planar straight-line grid drawing with $O(n^2)$ area, and in the worst case it requires $\Omega(n^2)$ area. It is also known that a binary tree with $n$ nodes admits a planar straight-line grid drawing with $O(n)$ area. Thus, there is wide gap between the $\Theta(n^2)$ area-requirement of general planar graphs and the $\Theta(n)$ area-requirement of binary trees. It is therefore important to investigate special categories of planar graphs to determine if they can be drawn in $o(n^2)$ area. Outerplanar graphs form an important category of planar graphs. We investigate the area-requirement of planar straight-line grid drawings of outerplanar graphs. Currently the best known bound on the area-requirement of such a drawing of an outerplanar graph with $n$ vertices is $O(n^2)$, which is that same as for general planar graphs. Hence, a fundamental question arises that can be draw an outerplanar graph in this fashion in $o(n^2)$ area? In this paper, we provide a partial answer to this question by proving that an outerplanar graph with $n$ vertices and degree $d$ can be drawn in this fashion in area $O(dn^{1.48})$ in $O(n\log n)$ time. This implies that an outerplanar graph with $n$ vertices and degree $d$, where $d= o(n^{0.52})$, can be drawn in this fashion in $o(n^2)$ area. From a broader perspective, our contribution is in showing a sufficiently large natural category of planar graphs that can be drawn in $o(n^2)$ area. %Z Mon, 22 Sep 2003 14:44:07 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-13.pdf %A Yu, Xiang, Qiao, Chunming , Liu, Yong and Towsley, Don %T Performance Evaluation of TCP Implementations in OBS Networks %R 2003-13 %D July 1, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Optical Burst Switching, TCP, Reno, SACK, Performance modeling %Y Computer Communications Networks, Network Protocol, C.2.2 %X Since TCP traffic is and may remain as the most popular traffic type in the Internet, it is important to evaluate the performance of TCP in networks employing optical burst switching (OBS), a promising paradigm for the next generation Optical Internet. This work is the first comprehensive study of the TCP performance in OBS networks. Our results provide valuable insights into the interactions between the TCP congestion control mechanism and OBS-specific mechanisms such as burst assembly/disassembly and buffer-less burst switching. In particular, we identify various factors that result in TCP throughput gains and penalties, and determine optimal burst assembly times to be used in OBS networks. In addition, TCP throughput models are developed for the three most popular TCP implementations, i.e., SACK, Reno and New-Reno, and are validated through simulations. %Z Mon, 12 Jan 2004 20:47:53 GMT %U http://www.cse.buffalo.edu/tech-reports/2003-12.pdf %A Garg, Ashim %A Rusu, Adrian %T A More Practical Algorithm for Drawing Binary Trees in Linear Area with ArbitraryAspect Ratio %R 2003-12 %D September 19, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K tree, drawing, area, aspect ratio, straight-line, planar %X Trees are usually drawn planar, i.e. without any edge-crossings. It is important to minimize the area of a drawing, so that it can fit within the given drawing-window. It is also important to give user some control over the aspect ratio of the drawing, so that she can display the drawing in a drawing-window with arbitrary width-to-height ratio. In a grid drawing, each node is assigned integer coordinates. In~\cite{gr-sldbt-02}, it was shown that any binary tree with $n$ nodes admits a planar straight-line grid drawing with area $O(n)$ and with any pre-specified aspect ratio in the range $[n^{-\epsilon},n^\epsilon]$, where $\epsilon$ is any constant such that $0 < \epsilon < 1$. It was also shown that such a drawing can be constructed in $O(n\log n)$ time. In particular, this showed that optimal area (equal to $O(n)$) and optimal aspect ratio (equal to 1) is simultaneously achievable for such drawings. However, the algorithm of~\cite{gr-sldbt-02} is not suitable for practical use. The main problem is that the constant $c$ hidden in the ``Oh'' notation for area is quite large (for example, it can be as high as 3900). In this paper, we make several non-trivial practical improvements to the algorithm, which make it suitable for practical use. We have also conducted experiments on this newer version of the algorithm for randomly-generated binary trees with up to 50,000 nodes, and for complete binary trees with up to $65,535=2^{16}-1$ nodes. Our experiments show that it constructs area-efficient drawings in practice, with area at most 8 times the number of nodes for complete binary trees, and at most 10 times the number of nodes for randomly-generated binary trees. %Z Tue, 02 Mar 2004 14:42:54 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-06.pdf %A Ghosh, Joy %A Kumar, Vivek %A Wang, Xin %A Qiao, Chunming %T BTSpin - Single Phase Distributed Bluetooth Scatternet Formation %R 2004-06 %D December 13, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Bluetooth, Wireless Networking, Scatternet formation %Y algorithm, design %X The Bluetooth standard specifies the formation of Piconets but only alludes to the possibility of joining several of these Piconets to form a Scatternet. In an attempt to formalize this Scatternet formation process, several schemes have been suggested. The centralized schemes suggested so far, require all the nodes to be in the radio range of each other (i.e. single hop) to ensure the correctness of their algorithm. To address multi hop scenarios, the distributed schemes suggested so far, usually require multiple phases to form a Scatternet. In particular, they need a considerable amount of time and energy in the topology discovery phase, during which the nodes exchange one hop or even two hop neighbor information. This also restricts these schemesĀ? ability to efficiently cope with fully dynamic topology changes due to nodes joining/leaving. In this work, we propose a novel and practical approach called BlueToothSpin (BTSpin) to overcome several of the above mentioned shortcomings. BTSpin has a single phase, wherein the nodes concurrently form Scatternets and route data traffic. Our simulations show that BTSpin has a low Scatternet formation delay, and can form efficient multi-hop Scatternets when nodes arrive both Incrementally and En Masse (all at the same time). The total number of Piconets formed and the average number of roles per node (number of Piconets a node participates in) are also shown to be lower than other proposed mesh based protocols. %Z Mon, 22 Mar 2004 19:01:39 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-03.ps %A Glasser, Christian %A Pavan, A. %A Selman, Alan %A Sengupta, Samik %T Properties of NP-Complete Sets %R 2004-03 %D January 15, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K clossness, immunity, pseudorandom generators, secure one-way permutations, disjoint NP-pairs %X We study several properties of sets that are complete for NP. We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is $\redm$-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$ such that for every $L \in \NP - \P$, $L - S$ is not many-one-hard for NP. Moreover, we prove for every $L \in \NP - \P$, that there exists a sparse $S \in \EXP$ such that $L - S$ is not many-one-hard for NP. Hence, removing sparse information in P from a complete set leaves the set complete, while removing sparse information in EXP from a complete set may destroy its completeness. Previously, these properties were known only for exponential time complexity classes. We use hypotheses about pseudorandom generators and secure one-way permutations to resolve longstanding open questions about whether NP-complete sets are immune. For example, assuming that pseudorandom generators and secure one-way permutations exist, it follows easily that NP-complete sets are not p-immune. Assuming only that secure one-way permutations exist, we prove that no NP-complete set is $\DTIME(2^{n^\epsilon})$-immune. Also, using these hypotheses we show that no NP-complete set is quasipolynomial-close to P. We introduce a strong but reasonable hypothesis and infer from it that disjoint Turing-complete sets for NP are not closed under union. Our hypothesis asserts existence of a $\UP$-machine $M$ that accepts $0^*$ such that for some $0 < \epsilon < 1$, no $2^{n^{\epsilon}}$ time-bounded machine can correctly compute infinitely many accepting computations of $M$. We show that if $UP \cap coUP$ contains $\DTIME(2^{n^\epsilon})$-bi-immune sets, then this hypothesis is true. %Z Mon, 22 Mar 2004 19:06:47 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-02.pdf %A Zhao, Dan %T An Integrated Framework for Concurrent Test and Wireless Control in Complex SoCs %R 2004-02 %D December 30, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K SOC test, test cost, resource partitioning, test scheduling, test access, wireless test control %Y Design; Reliability %X System-on-chip (SoC) is evolving as a new design style, where an entire system is built by reusing pre-designed, pre-verified IP (intellectual property) cores. Embedded with numerous heterogeneous and complex IP cores, an SoC can be viewed as an interconnected network of various functional modules. This new design style shortens time-to-market while meeting various design requirements, such as high performance, low power, and low cost, compared to the traditional system-on-board (SoB) design. In the meantime, however, embedded core-based SoC test becomes a challenging task due to IP protection. In particular, there are three major issues to be addressed in SoC test: (1) a test access path needs to be constructed for each core to propagate test stimulus and collect test responses, (2) one needs to partition test resources and schedule IP cores to achieve maximum parallelism, and (3) a test control network is needed to initialize different test resources used in the test application and observe the corresponding test results at appropriate instants. In this dissertation, we develop cost-effective SoC test and diagnosis solutions from various crucial aspects, such as test time, test access architecture, and memory depth on automatic test equipment (ATE). It is the very first work that introduces radio frequency (RF) technology into SoC test control for the forthcoming billion-transistor era. We mainly address two research issues: integrated testability design and optimization of SoC test solutions, and on-chip wireless test control network design. We first develop a general test model for SoC testability analysis, test scheduling, and test diagnosis. We then propose several test scheduling algorithms with the consideration of various test constraints such as resource sharing, power dissipation, and fault coverage, and develop an integrated framework that combines wrapper design, test access mechanism (TAM) configuration, and test scheduling. More specifically, we propose a fault model oriented test set selection scheme and formulate the test scheduling as a shortest path problem with the feature of evenly balanced resource usage. We also propose a dynamic test partitioning technique based on the test compatibility graph to address the power-constrained test scheduling problem. Furthermore, we develop an integrated framework to handle constrained scheduling in a way that constructs core access paths and distributes TAM bandwidth among cores, and consequently configures the wrapper scan chains for TAM width adaptation. Using the "Radio-on-Chip" technology, we introduce a novel test control network to transmit control signals chip-wide by RF links. We propose three types of wireless test control architectures, i.e., a miniature wireless local area network, a multihop wireless test control network, and a distributed multihop wireless test control network. The proposed architectures consist of three basic components, namely the test scheduler, the resource configurators, and the RF nodes supporting the communication between the scheduler and the IP cores. Under the multilevel tree structure, the system optimization is performed on control constrained resource partitioning and distribution. Several challenging system design issues such as RF nodes placement, clustering, and routing, are studied along with integrated resource distribution (including not only the circuit blocks to perform testing, but also the on-chip RF nodes for intra-chip communication) and test scheduling (concurrent core testing as well as interconnect testing). Cost oriented optimization technique is developed which addresses several highly interdependent design issues to achieve the minimum overall testing cost. %Z Mon, 22 Mar 2004 19:06:54 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-04.ps %A Tambay P. and Jayaraman B. %T Implementation Techniques for Constrained Objects %R 2004-04 %D February 29, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K constraints, objects, translation, partial evaluation, debugging, constraint satisfaction %X This paper presents the implementation of constrained objects. A constrained object is an object whose attributes are subject to constraints. When a constrained object aggregates other objects, it may impose further constraints on the attributes of these objects. As shown in a recent paper, this programming paradigm is very useful for modeling various systems, especially in the engineering domain. Here, a constraint may be simple, quantified, conditional, or non-linear. A constrained object (Cob) program consists of Java-like class definitions except that methods are replaced by constraints. These constraints may also refer to user-defined CLP-like predicates. Hence our implementation is based on a translation from Cob classes to CLP predicates. Execution of the translated CLP predicates will not yield adequate performance for large-scale systems. Hence we develop a partial execution technique for optimized code generation. This approach also enables developing a visual debugger for Cob programs and also interfacing with a system such as Maple for solving non-linear constraints. The paper presents the syntax and examples of Cob programs, and the scheme for translation and partial execution. The techniques described in this paper have been implemented. %Z Mon, 22 Mar 2004 19:07:02 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-05.ps %A Raux R.J. and Jayaraman B. %T Modeling Dynamic Systems with Constrained Objects %R 2004-05 %D February 29, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K constraints, objects, dynamic system, state change, temporal constraints %X This paper examines the application of constrained objects for modeling dynamic systems. A dynamic system is one whose state changes with time. A constrained object is an object whose internal state is governed by a set of (declarative) constraints. When a complex system is modeled as a set of constrained objects, the resultant behavior is deduced through a process of constraint satisfaction. In previous research, we explored the paradigm of constrained objects for modeling the steady-state behavior of systems. In this paper, we present extensions that allow time-depedent behavior to be modeled as well. A key feature of our proposed approach is that of a time-series variable whose values are in accordance with specified constraints. We provide examples from diverse domains (AC circuits, hydrological modeling, and sensor networks) to illustrate our approach. We are developing a prototype that includes a compiler that translates Cob programs into Sicstus Prolog Objects with CLP(R) constraints. %Z Mon, 22 Mar 2004 19:07:05 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-01.ps %A Selman, A. %A Sengupta, S. %T Polylogarithmic-round Interactive Proofs for coNP %R 2004-01 %D September 02, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %Z Mon, 22 Mar 2004 19:59:48 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-08.pdf %A Ghosh, Joy %A Philip, Sumesh %A Qiao, Chunming %T ORBIT Mobility Framework and Orbit Based Routing (OBR) Protocol for MANET %R 2004-08 %D July 12, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K Mobility models, Routing protocol, Ad hoc wireless networks, Performance analysis %X A major hurdle in evaluating routing protocols for a Mobile Ad Hoc NETwork (MANET) is the appropriate modeling of the mobility of wireless nodes. Although the pure random nature of the Random Waypoint model lends itself for theoretical study of MANET protocols, it is not suitable for modeling the movements of mobile nodes in real scenarios. To this end, several entity, group and scenario based mobility models and frameworks have been proposed in literature for representing node mobility. Some of these models cater to only short term applications of ad hoc networks (e.g., disaster, military), while others are based on complex scenario parameters (e.g., buildings, pathways). In this paper, we propose a novel mobility framework called ORBIT. In addition to generating a more practical mobility pattern based on sociological movement of users, ORBIT can also integrate all the work mentioned above into a single framework. The proposed ORBIT framework is applicable to all kinds of wireless networks (cellular, ad hoc etc.) and is also capable of generating different models to suit either short term or long term network mobility in various scenarios. We also propose an Orbit Based Routing (OBR) protocol for MANETs, which takes advantage of the ORBIT framework and outperforms other routing protocols like Dynamic Source Routing (DSR) and Location Aided Routing (LAR). %Z Tue, 13 Jul 2004 18:15:44 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-07.ps %A Karthik Sundararaman %T Design For Manufacturability - Fault Model Extensions for RF Circuits with an Economic Perspective for Manufacturability %R 2004-07 %D May 18, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K LNA, Cost Modeling, Fault Models, DFT, Reliability %Y Economics; Reliability; VLSI Testing %X Design For Manufacturability issues have started escalating the problem of Design and Test in the Deep Submicron era. Two questions posed are "How good is the quality?" and "How expensive is the product?" To ensure quality one needs to answer the question "To DFT or Not to DFT." New Analog and RF designs lack good DFT techniques due to inadequate fault models. Using existing test techniques that are largely outdated, one has to and out if the solutions are economically feasible for the vendor to implement in his designs. The quality issues of RF cores and the economic issues of mixed signal cores and standalone chipsets are addressed in this thesis from a DFM standpoint. A lot of emphasis has been placed on the test cost of chips and a variety of models have been proposed in the literature. Existing models are incomplete with the fact that most do not take into account the costs involved once the chip reaches the market. This thesis focuses on the cost economics of fault tolerant chips and how RF cores fit into the whole economic model for new designs. New fault models which could help improve the testability of circuits (hence improving quality) are discussed here. The focus is then moved to an economic cycle where mathematical estimates of the costs for new designs are given. This model will help designers analyze the need for a fault tolerant system and its feasibility in the industry using the reliability of the system. It will help evaluate the costs involved during the life cycle of a chip. Design tools - SpectreRF and ASITIC have been used for modeling RF circuits at 0.25u technology. Carafe tool has been used to perform fault analysis on the layout of the circuit to model realistic faults. Existing fault models for resistors and capacitors have been verified and a new fault model for inductors has been proposed using these tools. The fault models will help improve the design of RF circuits by enforcing more constraints on design specific issues. The cost models proposed in this thesis will help designers identify key areas of cost and help clamp down unnecessary expenses where possible. %Z Fri, 13 Aug 2004 19:04:00 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-12.ps %A Srikanth, Munirathnam %T EXPLOITING QUERY FEATURES IN LANGUAGE MODELING APPROACH\\FOR INFORMATION RETRIEVAL %R 2004-12 %D August 26, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K information retrieval, statistical language modeling, biterms, concept language model, maximum entropy language models %X Statistical Language Modeling has recently been applied to the problem of Information Retrieval~(IR) and appreciable performance improvements have been achieved over traditional vector space and probabilistic retrieval models. Most experiments demonstrating the language modeling approach to text retrieval have been based on smoothed unigram language models that only exploit the term occurrence statistic in probability estimation. Experiments with additional features like bigrams have met with limited success. However, language models incorporating $n$-gram, word-triggers, topic of discourse, syntactic and semantic features have shown significant improvements in speech recognition. The main thrust of this dissertation is to identify the need to {\em design} language models for IR that satisfy its specific modeling requirements and demonstrate it by designing language models that (1) incorporate IR-specific features~(biterm language model), (2) correspond to better document and query representations~(concept language model) and (3) combine evidence from the different information sources~(language features) towards modeling the relevance of a document to a given query~(maximum entropy language models for IR). Prior research in incorporating additional features in language models for information retrieval have adopted models derived for speech recognition. However, speech recognition and information retrieval have different language modeling requirements. For example, in speech recognition the utterances {\em information retrieval} and {\em retrieval of information} should be distinguished; whereas they should have same representation for efficient information retrieval. {\em Biterm Language Models} -- a variant of bigram language models -- are introduced here to address this problem. Biterm language models handle the local variation - within 2 words - in the surface form of words used in the expression of a concept. It is, however, these concepts that need to be modeled in the queries to improve retrieval performance. {\em Concept Language Models}~(CLM) that prescribe a two-layered query model is presented in this dissertation. A user's information need is modeled as a sequence of concepts and the query is viewed as an expression of such concepts of interest. It is shown that such a model provides significant improvements to retrieval performance. CLM also provide a natural way of incorporating concept synonymy in the language modeling approach to IR. Mixture models combine statistical evidence from different sources to estimate the probability distribution. For example, smoothed unigram language model for a document combines unigram counts from the document and corpus. While mixture models are easy to implement, they seem to make suboptimal use of their components. A natural method of combining information sources based on the Maximum Entropy Principle has been shown to contribute significantly to perplexity reduction and hence better language models for speech recognition. Such a framework is proposed for information retrieval in the context of document likelihood or relevance language models. The {\em maximum entropy language model} for information retrieval provides a better mechanism for incorporating external knowledge and additional syntactic and semantic features of the language in language models for IR. %Z Fri, 27 Aug 2004 19:59:23 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-13.pdf %A Liu, Jiangjiang %T INFORMATION PATTERN AWARE DESIGN STRATEGIES FOR NANOMETER-SCALE ADDRESS BUSES %R 2004-13 %D August 31, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K computer system design, memory system, address bus, power consumption, performance, cost, data compression %Y Design %X The growing disparity in processor and memory performance has forced designers to allocate an increasing fraction of die area to communication (I/O buffers, pads, pins, on- and off-chip buses) and storage (registers, caches, main memory) components of the memory system to enable low-latency and high-bandwidth access to large amounts of information (addresses, instructions, and data). Consequently, the memory system has become critical to system performance, power consumption, and cost. In this dissertation, we consider three types of redundancies related to information communicated and stored in the memory system, with the main focus being on information communicated on nanometer-scale address buses. They are temporal redundancy , information redundancy, and energy redundancy. To take advantage of these redundancies, we analyze and design information pattern aware strategies to exploit various patterns in information communicated and stored in a multi-level memory hierarchy to derive gains in performance, energy efficiency, and cost. Our main contributions are as follows. (1) A comprehensive limit study on the benefits of address, instruction, and data compression at all levels of the memory system considering a wide variety of factors. (2) A technique called hardware-only compression (HOC), in which narrow bus widths are used for underutilized buses to reduce cost, novel encoding schemes are employed to reduce power consumption, and concatenation and other methods are applied to mitigate performance penalty. (3) A detailed analysis of the performance, energy, and cost trade-offs possible with two cache-based dynamic address compression schemes. (4) A highly energy- and performance-efficient dynamic address compression methodology for nanometer-scale address buses. Many of the principles underlying this methodology are also applicable to instruction and data bus compression. All our analysis and design has been performed in the context of real-world benchmark suites such as SPEC CPU2000 and using execution-driven simulators like Shade and SimpleScalar. Our analysis shows that ample opportunities exist for applying compression throughout the memory system. Further, we show that our address compression methods can simultaneously provide significant improvements in energy efficiency, cost, and latency compared to an uncompressed bus. %Z Wed, 01 Sep 2004 13:04:29 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-14.pdf %A Ghosh, Joy %A Philip, Sumesh %A Qiao, Chunming %T Performance Analysis of Mobility Based Routing Protocols in MANET %R 2004-14 %D September 16, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K Mobility model, Routing protocol, Ad hoc wireless networks, Performance analysis %X Most routing protocols in MANET adopt the popular Random Waypoint model for its simplicity and suitability for theoretical study and analysis. Recently, several entity, group and scenario based mobility models and frameworks have been proposed to model much more realistic and practical movements of mobile nodes in real scenarios. Although some work exists in evaluating routing protocols based on such specific scenarios, and some effort in adapting a protocol to suit mobility has been made, there does not exist any protocol that makes direct use of mobility information to route packets within a MANET. In this work, we first develop a practical mobility model that recognizes an orbital pattern in the sociological movement of mobile users, and then propose a novel Orbit Based Routing (OBR) protocol, that leverages the underlying orbital mobility to accurately determine a set of likely regions containing any node in the MANET. By forming a distributed location database among acquaintances and employing a scalable geographic routing to forward packets among nodes, OBR emerges as a clear choice for MANET routing in the face of practical mobility. We propose three different schemes of OBR and compare their performance against an Acquaintance Based Soft Location Management (ABSoLoM) protocol. %Z Fri, 17 Sep 2004 13:50:47 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-09.pdf %A Aruna Balasubramanian, Sumita Mishra and Ramalingam Sridhar %T A Hybrid Approach to Key Management for Enhanced Security in Ad Hoc Networks %R 2004-09 %D July 30, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K Ad hoc networks, Security, Key management, Symmetric cryptosystems, Asymmetric cryptosystems, Threshold cryptography, Clustering %X Key management is one of the most challenging tasks in developing security solutions for wireless ad hoc networks. Most of the security primitives can only be realized if an efficient, robust and secure key generation and management system is developed. Symmetric key cryptosystems are difficult to incorporate in an ad hoc decentralized domain, and are not scalable. A public key cryptosystem is computationally expensive and a decentralized certification service is essential for its deployment. In this paper, we present a locally symmetric/globally asymmetric key management solution for wireless ad hoc networks that overcomes the limitations of both. The proposed hybrid approach does not require prior trust assumptions or the presence of a centralized certification authority. Preliminary analysis and results indicate that this approach can achieve a better performance when compared with the traditional solutions. We show that our approach is scalable, and robust with respect to node failures, topology changes, node speed and loss of connectivity. %Z Wed, 29 Sep 2004 14:00:58 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-15.pdf %A Yu, Xiang %A Thng, Ian %A Jiang, Yuming %A Qiao, Chunming %T Queuing Processes in GPS and PGPS with LRD Traffic Inputs (Extended Version) %R 2004-15 %D September 29, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K long range dependent, generalized processor sharing %X Long range dependent (LRD) traffic whose single server queue process is Weibull Bounded (WB) is first analyzed. Two upper bounds on the individual session's queue length of LRD traffic under the generalized processor sharing (GPS) scheduling discipline are then contributed. It is shown that the index parameter in the upper bound of one LRD flow may be affected by other LRD flows. A new concept, called LRD isolation, is subsequently contributed and accompanying it, a new technique is contributed to check whether a flow, with a given GPS weight assignment, can be guaranteed to be LRD isolated. This technique is also amenable for an online call admission control (CAC) to determine minimum contract weights of a new flow in order to guarantee the LRD isolation. The results are also extended to a PGPS (Packet-based GPS) scheduler and relevant numerical results are provided to show the usefulness of our bounds and LRD isolation technique. %Z Wed, 29 Sep 2004 19:33:49 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-16.pdf %A Chinchani, Ramkumar %A Iyer, Anusha %A Ngo Q., Hung %A Upadhyaya, Shambhu %T A Target-Centric Formal Model For Insider Threat And More %R 2004-16 %D October 12, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K Computer Security, Threat Analysis, Insider Threat %Y Security, Algorithms %X The diversity of cyber threat has grown over time from network-level attacks and password-cracking to include newer classes such as insider attacks, email worms and social engineering, which are currently recognized as serious security problems. However, attack modeling and threat analy- sis tools have not evolved at the same rate. Known formal models such as attack graphs perform action-centric vulnerability modeling and analysis. All possible atomic user actions are represented as states, and sequences which lead to the violation of a specified safety property are extracted to indicate possible exploits. While attack graphs are relevant in the context of network level attacks, they are ill-equipped to address complex threats such as insider attacks. The difficulty mainly lies in the fact that adversaries belonging to this threat class use familiarity of and accessibility to their computational environment to discover new ways of launching stealthy, damaging attacks. In this paper, we propose a new target-centric model to address this class of security problems and explain the modeling methodology with specific examples. Finally, we perform quantified vulnerability analyses and prove worst case complexity results on our model. %Z Tue, 12 Oct 2004 19:55:48 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-17.ps %A Glasser, Christian %A Selman, Alan L. %A Zhang, Liyu %T Canonical Disjoint NP-Pairs of Propositional Proof Systems %R 2004-17 %D November 19, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K disjoint NP-pairs, propositional proof systems, canonical pairs, degrees %Y F.1.3 %X We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is identical. Secondly, we show that this degree structure is not superficial: Assuming there exist P-inseparable disjoint pairs, there exist intermediate disjoint NP-pairs. That is, if $(A, B)$ is a P-separable disjoint NP-pair and $(C, D)$ is a P-inseparable disjoint NP-pair, then there exist P-inseparable, incomparable NP-pairs $(E, F)$ and $(G, H)$ whose degrees lie strictly between $(A, B)$ and $(C, D)$. Furthermore, between any two disjoint NP-pairs that are comparable and inequivalent, such a diamond exists. %Z Fri, 19 Nov 2004 19:20:45 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-18.ps %A Mathew, Sunu %A Shah, Chintan %A Upadhyaya, Shambhu %T An Alert Fusion Framework for Situation Awareness of Coordinated Multistage Attacks %R 2004-18 %D November 29, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K Alert Fusion, Computer Security, Intrusion Detection, Situation Awareness %X Recent incidents in the cyber world strongly suggest that coordinated multistage cyber attacks are quite probable and that effective countermeasures need to be developed. Attack detection by correlation and fusion of intrusion alerts has been an active area of current research. However, most of these research efforts focus on ex post facto analysis of alert data to uncover related attacks. In this paper, we present an approach for dynamically calculating `Scenario Credibilities' based on the state of a live intrusion alert stream. We also develop a framework for Attack Scenario representation that facilitates real-time fusion of intrusion alerts and calculation of the scenario credibility values. Our approach provides a usable mechanism for detecting, predicting and reasoning about multistage goal-oriented attacks in real time. The details of the fusion framework and a description of multistage attack detection using this framework are presented in this paper. %Z Wed, 01 Dec 2004 13:46:20 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-19.ps %A Girgis, Hani Z. %A Hegde, Akshay V. %A Pushpendran, Manu %A Gestwicki, Paul V. %A Jayaraman, Bharat %T Visual Queries for Interactive Execution of Java Programs %R 2004-19 %D December 13, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K visual query, program execution database, interactive execution, java, jive %X The behavior of object-oriented programs at runtime can be understood in terms of object states and the history of interaction between objects. Runtime behavior can be very complicated, and information visualization tools are invaluable for program development and debugging. While there has been considerable work in predicting execution patterns through slicing and program analysis, comparatively less has been done on analysis of program execution states and histories. We present a novel technique for visualizing queries over object-oriented program execution. Our technique is built upon the JIVE system of interactive program visualization, which depicts program state in object diagrams and execution history through sequence diagrams. The queries are posed through the graphical interface, and each view of a program (state, history, source code) provides different querying functionality. Furthermore, the results of the queries are shown in the graphical user-interface by annotating the diagrams or inducing new views. Our design allows for queries over variables, methods, objects, classes, and source code. This paper describes the domain of these queries as well as their interfaces, briefly outlines their implementation, and also provides a survey of related work and comparisons. %Z Wed, 15 Dec 2004 19:51:21 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-20.ps %A Gestwicki, Paul V. %A Jayaraman, Bharat %T Methodology and Architecture of JIVE %R 2004-20 %D December 13, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K interactive execution, object-oriented program visualization, forward and reverse execution, object diagrams, sequence diagrams, java, jive %X A novel approach to the runtime visualization and analysis of object-oriented programs is presented and illustrated through a prototype system called JIVE: Java Interactive Visualization Environment. The main contributions of JIVE are in its multiple concurrent representations of program state and execution history through an environment that supports forward and reverse execution along with execution queries. This model facilitates program understanding and interactive debugging. Our graphical representation of runtime states clarifies the important point that objects are execution environments. The history of object interaction is displayed via sequence diagrams similar to those of the Unified Modeling Language, and in this way we help close the loop between design-time and run-time representations. Interactive execution is made possible by maintaining a runtime history database, which may be queried for information on variable behavior, method executions, and object interactions. We illustrate the capabilities of this system through examples. JIVE is implemented using the Java Platform Debugger Architecture and supports the Java language and libraries, including multithreaded and GUI applications. %Z Thu, 16 Dec 2004 13:26:53 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-22.ps %A Glasser, Christian %A Ogihara, Mitsunori %A Pavan, A. %A Selman, Alan L. %A Zhang, Liyu %T Autoreducibility, Mitoticity, and Immunity %R 2004-22 %D December 21, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K autoreducibility, mitoticity, immunity %X We show the following results regarding complete sets: NP-complete sets and PSPACE-complete sets are many-one autoreducible. Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are many-one autoreducible. EXP-complete sets are many-one mitotic. NEXP-complete sets are weakly many-one mitotic. PSPACE-complete sets are weakly Turing-mitotic. If one-way permutations and quick pseudo-random generators exist, then NP-complete languages are m-mitotic. If there is a tally language in NP \cap coNP - P, then, for every \epsilon > 0, NP-complete sets are not 2^{n(1+\epsilon)}-immune. These results solve several of the open questions raised by Buhrman and Torenvliet in their 1994 survey paper on the structure of complete sets. %Z Wed, 22 Dec 2004 14:38:38 GMT %U http://www.cse.buffalo.edu/tech-reports/2004-21.ps %A Gestwicki, Paul V. %A Jayaraman, Bharat %A Garg, Ashim %T From Class Diagrams to Object Diagrams: An Automated Approach %R 2004-21 %D December 13, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K class diagram, object diagram, graph drawing, interactive program execution, jive %X This paper addresses the problem of how to visually depict the object structures that arise during the execution of object-oriented programs. Such a need arises in systems for run-time visualization of object-oriented programs. A straightforward approach would be to treat the object structure as a directed graph and apply traditional graph drawing techniques. However, we show that such an approach results in suboptimal drawings since important structural information in the class diagram is overlooked. A more effective approach must utilize properties of the class diagram in guiding a traditional graph-drawing approach. In particular, objects that are instances of related classes should be drawn in proximity to one another. The contribution of this paper lies in providing a formal definition of two important properties that yield predictable object diagrams: recursive cluster and leaf cluster. While the former commonly occur in structures such as lists, trees, etc., the latter are motivated by the power law property of object graphs, namely, that there are very few objects with high degree and many with low degree. This paper shows that these properties can be efficiently detected in the class diagram, and also efficiently applied to produce aesthetic object diagrams. The techniques described in this paper form the basis for the rendering of object structures in the JIVE system for interactive visualization of Java programs. %Z Mon, 03 Jan 2005 15:07:09 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-01.ps %A Santore, John F. %T Complete Coded Protocols from PIO Experiment %R 2005-01 %D January 05, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %X The complete text of all coded transcripts used as data for John Santore's dissertation can be found in this file. Both the coded transcripts and the retrospectives (for the 95% of participants who gave them) are included. The transcripts are organized by the temporary task numbers that they were given during the experiment. Those are: Task 1: Counting immobile classes in a four room suite wherein each room has a different appearance Task 2: Counting immobile classes in a four room suite wherein the opposite rooms have the same appreance Task 3: Counting Mobile robots that all looked alike. Task 4: Following a robot with randomly moving PIO distractors Task 5: Counting Mobile robots with 3 being silver-gray and two being red-gold. Task 6: Following a robot with PIO distractors that followed paths of their own Task 7: The Control task. Following a person with other people as the distractors. For more details see John F. Santore's dissertation. %Z Fri, 07 Jan 2005 15:38:46 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-04.ps %A Tang, C., Ramanathan, M., Jiang, D., and Zhang, A. %T A Semi-Supervised Learning Method for Coherent Pattern Detection from Gene-Sample-Time Series Datasets %R 2005-04 %D March 09, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K Gene-sample-time microarray data, semi-supervised learning %Y Algorithms %X DNA microarrays provide simultaneous, semi-quantitative measurements of the expression levels of thousands of genes from a single experimental sample. The availability of such data sets can enhance our understanding of gene function and regulation if the patterns underlying gene expression data can be identified. In this paper we study the problem of coherent pattern detection from gene-sample-time series expression data sets. These data sets result from microarray experiments in which a gene expression time series obtained on multiple samples using microarrays; the gene identities represent the first dimension, the sample properties represent the second dimension and time represents the third dimension. Such Gene-Sample-Time Series (GST) data arise naturally in microarray experimental designs, e.g., when the pharmacodynamics of gene expression in responder and non-responder groups is investigated. A new semi-supervise learning method is proposed to search coherent blocks from gene-sample-time series data set. Each block contains a subset of genes and a subset of samples such that the patterns within the block are coherent along the time series. The coherent blocks may identify the samples corresponding to some phenotypes (e.g., disease states), and suggest the candidate genes correlated to the phenotypes. We empirically evaluate the performance of our approaches on a real microarray data of the pharmacodynamics of gene expression in multiple sclerosis patients after interferon beta treatment. %Z Thu, 10 Mar 2005 16:34:20 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-05.pdf %A Chinchani, Ramkumar %A Ha, Duc %A Iyer, Anusha %A Ngo, Hung Q. %A Upadhyaya, Shambhu %T On The Hardness of Approximating the Min-Hack Problem %R 2005-05 %D March 02, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K Inapproximability, Computer Security %X We study the hardness of approximation for the MINIMUM HACKING problem, which roughly can be described as the problem of finding the best way to compromise some target nodes given a few initial compromised nodes in a network. We give three reductions to show that MINIMUM HACKING problem is not approximable to within 2^((logn)^(1-\delta)) where \delta = 1-1/(loglog^c(n)), for any c < 1/2. In particular, the reductions are from a PCP, from the MINIMUM LABEL-COVER problem, and from the MINIMUM MONOTONE SATISFYING ASSIGNMENT problem. We also analyze some heuristics on this problem. %Z Fri, 11 Mar 2005 16:23:57 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-06.pdf %A Attias, H. T. %A Beal, M. J. %T Tree of Latent Mixtures for Bayesian Modelling and Classification of High Dimensional Data %R 2005-06 %D January 1, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %Y Algorithms %X Many domains of interest to machine learning, such as audio and video, computational biology, climate modelling, and quantitative finance, involve very high dimensional data. Such data are often characterized by statistical structure that includes correlations on multiple scales. Attempts to model those high dimensional data raise problems that are much less significant in low dimensions. This paper presents a novel approach to modelling and classification in high dimensions. The approach is based on a graphical model with a tree structure, which performs density estimation on multiple spatial scales. Exact inference in this model is computationally intractable; two algorithms for approximate inference using variational techniques are derived and analyzed. We discuss learning and classification using these algorithms, and demonstrate their performance on a handwritten digit recognition task. %Z Mon, 21 Mar 2005 16:28:31 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-09.pdf %A Ghosh, Joy %A Philip, Sumesh %A Qiao, Chunming %T Sociological Orbit Aware Routing in MANET %R 2005-09 %D March 25, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K Mobility models, Routing protocol, Ad hoc wireless networks, Performance analysis %X Mobility affects routing protocol performance within a Mobile Ad Hoc NETwork (MANET). Past research on mobility models and framework was motivated by the need to provide a simulation platform for evaluating routing protocol performance via realistic scenarios. Mobility information of individual nodes has also been used to improve routing decisions (e.g., choice of next hop, link break prediction) in a MANET. In this paper, we introduce a novel concept of integrating macro-mobility information obtained from the sociological movement pattern of mobile MANET users, into routing. The extraction of this mobility information is based on our observation that the movement of a mobile user exhibits a partially repetitive ?orbital? patten involving a set of ?Hubs? in practise. This partially deterministic movement pattern is both practical and useful in locating nodes and routing packets to them without the need for constant tracking or flooding. Leveraging this Hub-based orbital pattern, we propose a Sociological Orbit Aware Routing (SOAR) protocol. Through extensive performance analysis we show that SOAR significantly outperforms conventional routing protocols like Dynamic Source Routing (DSR) and Location Aided Routing (LAR) in terms of higher data throughput, lower control overhead, and lower end-to-end delay. %Z Wed, 13 Apr 2005 13:53:34 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-08.pdf %A Shapiro, Stuart C. %A Anstey, Josephine %A Pape, David E. %A Devdas Nayak, Trupti %A Kandefer, Michael %A Telhan, Orkan %T MGLAIR Agents in a Virtual Reality Drama %R 2005-08 %D March 30, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K Virtual Reality Drama; Intelligent Agents; Cognitive Architectures %X We provide an overview of the use of intelligent agents, implemented in the new MGLAIR architecture, in a virtual reality drama. For us, a virtual reality drama is a scripted play in which the computational agents are actors who have copies of the script, and one human audience member has been drafted to be a participant, but doesn't have a copy of the script. The computational actors must improvise reactions to the human partpicipant's actions, but keep the play moving along in as close agreement to the script as possible. The goal is to provide the human participant with a specific emotional experience. We explicate this philosophy; outline the previously described GLAIR architecture; explain the introduction of an organization into modalities that results in the new MGLAIR architecture; describe our current VR drama, The Trial, The Trail; and discuss the implementation of our actor-agents. Our discussion of the actor-agents focuses on their abilities to react to triggers (cues), their performance of contingent actions that are off the main-line arc of the script, their use of timers to pace the drama, and the organization of the cast of actor-agents into a multi-agent system. %Z Wed, 13 Apr 2005 13:53:44 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-07.ps %A Khan, Asheq %A Philip, Sumesh J. %A Qiao, Chunming %A Tripathi, Satish K. %T A Framework for Mobile Assisted Localization in Wireless Sensor Networks %R 2005-07 %D March 25, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K Localization, Sensor Network, Algorithm %X Location tracking has several applications in wireless sensor networks. While GPS receivers can be used for location awareness in the outdoor environment, it can be prohibitively expensive in terms of size, cost and power consumption for large scale deployment. Most of the existing work in network localization has investigated the problem of computing the locations of all nodes with the help of a limited subset of {\it seed} nodes, who are already aware of their own locations. In this work, we introduce the novel concept of mobile seed node assisted localization, in which a small subset of mobile sensor nodes are used for network localization. specifically, we consider the case in which the network is localized using only three mobile sensor nodes. We present efficient algorithms for network localization that optimizes the localization latency, total battery power and minimizes the maximal power consumption by any mobile sensor node. %Z Wed, 13 Apr 2005 19:51:20 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-12.pdf %A Ghosh, Joy %A Qiao, Chunming %A Philip, Sumesh %A Ngo, Hung %A Yoon, Seokhoon %T Sociological Orbit aware Location Approximation and Routing (SOLAR) in DTN %R 2005-12 %D April 6, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K Mobility framework, Routing protocol, Delay %X Routing in delay tolerant networks poses a challenging problem compared to a conventional data network due to the uncertainty and time varying nature of network connectivity. Initial research in this area has considered algorithms based on deterministic mobility of the nodes in DTN. While the assumption of deterministic mobility can lay the groundwork for a theoretical understanding of DTN, such knowledge may not be applicable to mobile ad hoc networks. In this work, we introduce a novel concept of a partially repetitive ?orbital? pattern of mobile users (nodes) involving a set of ?hubs?, that may be better suited for a semi-deterministic mobility modeling of DTN users. This partially deterministic movement pattern is both practical as well as useful in the sense that the hub list information can be useful for locating nodes and routing packets to them in a DTN. %Z Tue, 17 May 2005 19:26:02 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-11.pdf %A Staworko, Slawomir %A Chomicki, Jan %T Priority-Based Conflict Resolution in Inconsistent Relational Databases %R 2005-11 %D June 15, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K databases, inconsistencies,reparis, preferences %X We study here the impact of priorities on conflict resolution in inconsistent relational databases. We extend the framework based on the notions of repair and consistent query answer. We propose a set of postulates that an extended framework should satisfy and consider two instantiations of the framework: (locally preferred) l-repairs and (globally preferred) g-repairs. We study the relationships between them and the impact each notion of repair has on the computational complexity of repair checking and consistent query answers. %Z Thu, 16 Jun 2005 12:14:40 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-14.ps %A Huaming Zhang %A Xin He %T An Application of Well-Orderly Trees in Graph Drawing %R 2005-14 %D May 30, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %X Well-orderly trees seem to have the potential of becoming a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation \cite{BGH03,BGH0302}. Our application of well-orderly trees in this paper provides new evidence to their power. We give more compact visibility representation of plane graphs using the properties of well orderly trees. %Z Fri, 17 Jun 2005 17:44:26 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-15.ps %A Gestwicki, Paul V. %T Interactive Visualization of Object-Oriented Languages %R 2005-15 %D June 15, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K object-oriented programming; program visualization; interactive execution; java %X We present a novel approach for the interactive visualization of the execution of object-oriented programs that fulfills several important criteria: (i) visual depiction of the current execution state as well as the entire history of execution; (ii) support for forward as well as reverse execution stepping; (iii) enhanced graph-drawing techniques for the current state and history of execution; (iv) support for run-time queries on the execution state; (v) support for all major features of the Java language and use of the standard Java compiler and run-time system. Taken together, our approach marks a significant advance over existing techniques for visualizing object-oriented program execution. Our proposed notation for expressing Java execution states clarifies the important fact that objects are environments; that is, a method execution is shown within its object context. By incorporating diagrams similar to those used during the design phase, we help to close the loop between design and execution. In particular, an enhanced UML-like object diagram is used for depicting the current state, and sequence diagrams are used for execution history. Interactive execution is instrumented by conceptualizing program execution as a database, so that stepping backward or forward through recorded states involves rolling back or re-committing transactions. Our methodology incorporates a novel technique for recording minimal state transitions in order to efficiently provide this interactive execution. Automatically generating object and sequence diagrams requires advanced graph drawing techniques. The enhanced object diagrams we present are not simple graphs, and special techniques are required to process them. We illustrate how layered drawing techniques can be used to achieve good drawings of enhanced object diagrams. Two techniques are presented for automatically drawing sequence diagrams: a stochastic simulated annealing approach and a fast greedy technique. We show how traditional graph-theoretic approaches can be combined with program-specific properties in order to produce better automatic drawings. Specifically, an analysis of the class diagram is used to determine the classes that form logical clusters, and these clusters are formed in the object diagram generated at runtime. We have implemented our approach in a prototypical tool called JIVE: Java Interactive Visualization Environment. %Z Mon, 20 Jun 2005 19:13:48 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-16.pdf %A Rapaport, William J. %T Philosophy of Computer Science: An Introductory Course %R 2005-16 %D June 21, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K philosophy of computer science, philosophy of artificial intelligence, computer ethics %X There are many branches of philosophy called "the philosophy of X", where X = disciplines ranging from history to physics. The philosophy of artificial intelligence has a long history, and there are many courses and texts with that title. Surprisingly, the philosophy of computer science is not nearly as well-developed. This article proposes topics that might constitute the philosophy of computer science and describes a course covering those topics, along with suggested readings and assignments. This article is forthcoming in _Teaching Philosophy_, but without the appendices contained in this technical-report version that contain archived versions of the course webpages. %Z Wed, 22 Jun 2005 14:45:09 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-13.ps %A Santore, John F. %T Identifying Perceptually Indistinguishable Objects %R 2005-13 %D January 24, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %X This dissertation reports on an investigation into how Perceptually Indistinguishable Objects (PIOs) can be identified. An experiment with 68 human participants was performed to investigate how and how well people identify PIOs. The experiment was designed as a protocol analysis experiment. Participants performed a video-game like task of counting or following, both of which entail identifying objects. The analysis of this experiment shows that the human participants had a marked preference for certain situations that they believed helped them identify the PIOs more readily. Participants would try, as much as possible, to keep themselves in these situations. A cognitively plausible computational model of identifying PIOs is developed from the results of the human subjects experiment. The cues and strategies that participants in the experiment went out of their way to use are examined and treated separately. Some participant-preferred strategies always lead to the correct answer/identification when the participant's background beliefs are correct. These strategies are generally perceptually based and are called base cases. The other set of strategies that the participants tried to use are not quite as perceptually based and are called intermediate cases. These strategies, when correctly used, lead to the right answer a great deal of the time, but are slightly more prone to failure than the base cases. The knowledge needed for the general case of identifying PIOs is also discussed and an algorithm for the model is included. Finally, a new simulated cognitive robot is described that includes an implementation of the computational model of identifying PIOs. The robot was tested in the same environment that the human participants used for the experiments and on the same tasks. The mistakes that the robot made fell into a subset of the mistakes that the human participants made in the experiment. %Z Mon, 27 Jun 2005 17:33:33 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-17.pdf %A Ghosh, Joy %A Yoon, Seokhoon %A Ngo, Hung %A Qiao, Chunming %T Sociological Orbits for Efficient Routing in Intermittently Connected Mobile Ad Hoc Networks %R 2005-17 %D July 06, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K Mobility framework, Routing protocols, Intermittently Connected Networks, Theoretical model, Performance analysis %X Routing in Intermittently Connected Networks (ICN) is a challenging problem due to the uncertainty and time varying nature of network connectivity. In this work, we focus on a special class of ICN formed by mobile ad hoc users called ICMAN. We first consider a new and practical probabilistic mobility model where the nodes move between a set of ?hubs? in a partially repetitive and nondeterministic pattern to form the so-called ?sociological orbits?. Second, to leverage the sociological orbit based mobility pattern in routing within ICMAN, we propose a series of multi-path Sociological Orbit aware Location Approximation and Routing (SOLAR) protocols. We present theoretical analysis of the mobility model and routing algorithms under consideration, and show that the proposed routing algorithms can outperform other conventional routing approaches in an ICN by taking advantage of the sociological orbit based mobility pattern. %Z Mon, 11 Jul 2005 19:08:52 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-18.pdf %A Glasser, Christian %A Pavan, A. %A Selman, Alan L. %A Zhang, Liyu %T Redundancy in Complete Sets %R 2005-18 %D July 07, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K mitotic sets, autoreducibility, complete sets %X We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Gla{\ss}er et al., complete sets for all of the following complexity classes are m-mitotic: NP, coNP, $\oplus P$, PSPACE, and NEXP, as well as all levels of PH, MODPH, and the Boolean hierarchy overNP. In the cases of NP PSPACE, NEXP, and PH, this at once answers several well-studied open questions. These results tell us that complete sets share a redundancy that was not known before. We disprove the equivalence between autoreducibility and mitoticity for all polynomial-time-bounded reducibilities between 3-tt-reducibility and Turing-reducibility: There exists a sparse set in EXP that is polynomial-time 3-tt-autoreducible, but not weakly polynomial-time T-mitotic. In particular, polynomial-time T-autoreducibility does not imply polynomial-time weak T-mitoticity, which solves an open question by Buhrman and Torenvliet. We generalize autoreducibility to define poly-autoreducibility and give evidence that NP-complete sets are poly-autoreducible. %Z Mon, 11 Jul 2005 19:18:41 GMT %U http://www.cse.buffalo.edu/tech-reports/2005-19.pdf %A Glasser, Christian %A Selman, Alan L. %A Zhang, Liyu %T Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems %R 2005-19 %D July 07, 2005 %I Department of Computer Science and Engineering, SUNY Buffalo %K disjoint NP-pairs, propositional proof systems, canonical pairs, degrees %Y F.1.3 %Z Mon, 11 Jul 2005 19:18:53 GMT