%U ftp://ftp.cs.buffalo.edu/pub/tech-reports/90-12.ps.Z %A W. Rapaport %T Cognitive Science %R 90-12 %D May 1990 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/90-24.ps.Z %A X. He %T On Finding the Rectangular Duals of Planar Triangulated Graphs %R 90-24 %D 1990 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-04.ps.Z %A S. Homer %A A. Selman %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-05.ps.Z %A X. He %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-09.ps.Z %A J. Haas %A B. Jayaraman %T Automatic Synthesis of Semantics for Context-free Grammars %R 91-09 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-11.ps.Z %A B. Jayaraman %T The SuRE Programming Framework %R 91-11 %D 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? %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-12.ps.Z %A A. Selman %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-13.ps.Z %A S. Shapiro %A H. Chalupsky %A H. Chou %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-14.ps.Z %A A. Shende %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-16.ps.Z %A X. He %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/91-18.ps.Z %A K. Regan %A T. Schwentick %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-03.ps.Z %A S. Revankar %A D. Sher %T Supervised Image Segmentation %R 92-03 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-09.ps.Z %A E. Chuang %A D. Sher %T Tests for Feature Detection %R 92-09 %D 1992 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-10.ps.Z %A E. Chuang %A D. Sher %T Evidence Representation & Combination in Low-level Vision %R 92-10 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-12.ps.Z %A Tin Kam Ho %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-13.ps.Z %A S.Revankar %A D.Sher %T Pattern Extraction by Adaptive Propagation of a Regional Threshold %R 92-13 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-14.ps.Z %A S. Khoubyari %T The Application of Word Image Matching in Text Recogntion %R 92-14 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-18.ps.Z %A S. Sunder %A X He %T An NC Algorithm for Finding Minimum Weighted Completion Time Schedule on Series Parallel Graphs %R 92-18 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-21.ps.Z %A H. Hexmoor %A J. Lammens %A S. Shapiro %T An Autonomous Agent Architecture for Integrating Perception and Acting with Grounded Embodied Symbolic Reasoning %R 92-21 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-22.ps.Z %A D. Milun %A D. Sher %T Improving Edge Detectors on Compressed Images-A Trainable Markov Random Field Approach %R 92-22 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-24.ps.Z %A A. Jagota %A K. Regan %T Performance of MAX-CLIQUE Approximation Heuristics Under Description-Length Weighted Distributions %R 92-24 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-25.ps.Z %A S. Revankar %A D. Sher %T Constrained Contouring in the Polar Coordinates %R 92-25 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-26.ps.Z %A S. Chakravarty %A Y. Gong %T An Algorithm for Diagnosing Two-Line Bridging Faults in Combinational Circuits %R 92-26 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-27.ps.Z %A F. Green %A J. Kobler %A K. Regan %A T. Schwentick %A J. Toran %T The Power of the middle Bit of Number-P Function %R 92-27 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-30.ps.Z %A D. Sher %A K. Regan %T Constructing Noise-Reducing Operators from Training Images %R 92-30 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-32.ps.Z %A S. Chakravarty %A G. Theophilopoulos %T Computing Robust Test for Stuck-open Faults from Stuck-at Test Sets %R 92-32 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-33.ps.Z %A A. Jagota %T Approximating Maximum Clique with a Hopfield Network %R 92-33 %D 1992 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-01.ps.Z %A R. Sarnath %T Doubly logarithmic time parallel sorting %R 93-01 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-02.ps.Z %A R. Sarnath %T Lower bounds for padded sorting and approximate counting %R 93-02 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-04.ps.Z %A Sreejit Chakravarty %A Suresh Sivaprakasm %T I_DDQ Measurement Based Diagnosis of Bridging Faults in Full %R 93-04 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-05.ps.Z %A Stephen Fenner %A Steve Homer %A Mitsunori Ogiwara %A Alan L. Selman %T On Using Oracles That Compute Values %R 93-05 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-09.ps.Z %A Sreejit Chakravarty %A Yiming Gong %T A Diagnostic Simulation Algorithm for Stuck-at Faults in Combinational Circuits %R 93-09 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-10.ps.Z %A H. Hexmoor %A J. Lammens %A S. C. Shapiro %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-13.ps.Z %A J. Lammens %A H. Hexmoor %A S. C. Shapiro %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-15.ps.Z %A H. Hexmoor %A J. Lammens %A G. Caicedo %A S. C. Shapiro %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-16.ps.Z %A S. Ali %A S. C. Shapiro %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-18.ps.Z %A S. Sivaprakasam %T Performance Enhancements in SunOS NFS %R 93-18 %D May 1993 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-20.ps.Z %A Joongmin Choi %T Experience-Based Learning In Deductive Reasoning Systems %R 93-20 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-07.ps.Z %A Wei Shu %A Min-You Wu %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-24.ps.Z %A Kenneth W. Regan %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-25.ps.Z %A Kenneth W. Regan %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-26.ps.Z %A Mauricio Osorio %A Bharat Jayaraman %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-21.ps.Z %A Edith Hemaspaandra %A Ashish V. Naik %A Mitsunori Ogiwara %A Alan L. Selman %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-22.ps.Z %A R. Sarnath %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-31.ps.Z %A Johan M. Lammens %A Stuart C. Shapiro %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-30.ps.Z %A R. Bar-Yehuda %A V. Dabholkar %A K. Govindarajan %A D. Sivakumar %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-28.ps.Z %A Lane A. Hemaspaandra %A Ashish V. Naik %A Mitsunori Ogiwara %A Alan L. Selman %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}$. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-29.ps.Z %A Lane A. Hemaspaandra %A Albrecht Hoene %A Ashish V. Naik %A Mitsunori Ogiwara %A Alan L. Selman %A Thomas Thierauf %A Jie Wang %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-33.ps.Z %A Kenneth W. Regan %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-35.ps.Z %A Kenneth W. Regan %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-34.ps.Z %A Ashish V. Naik %A Kenneth W. Regan %A D. Sivakumar %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-37.ps.Z %A Henry H. Hexmoor %A Johan M. Lammens %A Stuart C. Shapiro %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-36.ps.Z %A Ashish V. Naik %A Alok Baveja %A Rajan Batta %A Jonathan P. Caulkins %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-23.ps.Z %A Niloufer Mackey %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-39.ps.Z %A David B. Sher %A Charlotte E. Wafford %A Davin Milun %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-02.ps.Z %A Jin-Yi Cai %A Ashish V. Naik %A Alan L. Selman %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-38.ps.Z %A Sreejit Chakravarty %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-40.ps.Z %A Bharat Jayaraman %A Mauricio Osorio %A Kyonghee Moon %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-01.ps.Z %A Syed S. Ali %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-03.ps.Z %A Sreejit Chakravarty %A Yiming Gong %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-42.ps.Z %A Sreejit Chakravarty %A Paul J. Thadikaran %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-04.ps.Z %A Deepak Kumar %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-23.ps.Z %A Henry Hexmoor, Donald Nute %T Methods for deciding what to do next and learning %R 92-23 %D September, 1992 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-06.ps.Z %A Sreejit Chakravarty, Vinay Dabholkar %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-07.ps.Z %A Henry H. Hexmoor %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-08.ps.Z %A Ishfaq Ahmad, Min-You Wu, Jaehyung Yang and Arif Ghafoor %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-09.ps.Z %A Henry H. Hexmoor %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-12.ps.Z %A Kannan Govindarajan, Bharat Jayaraman, Surya Mantha %T Preference Logic Programming: Optimization as Inference %R 94-12 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-10.ps.Z %A V.P. Dabholkar, S. Chakravarty %T Minimizing Power Dissipation in Combinational Circuits During Test Application %R 94-10 %D April 15, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-23.ps.Z %A Henry Hexmoor, Donald Nute %T Methods for deciding what to do next and learning %R 92-23 %D September, 1992 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-15.ps.Z %A Jin-Yi Cai %A Suresh Chari %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-14.ps.Z %A Jin-Yi Cai %A Michael D. Hirsch %T Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry %R 94-14 %D May 04, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-16.ps.Z %A Jin-Yi Cai %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-17.ps.Z %A Jin-Yi Cai %A Richard J. Lipton %A Yechezkel Zalcstein %T The complexity of the A B C problem resolved %R 94-17 %D May 12, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-19.ps.Z %A Frederic Green %A Johannes Koebler %A Kenneth W. Regan %A Thomas Schwentick %A Jacobo Toran %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-23.ps.Z %A Kenneth W. Regan %T Linear-Time Algorithms in Memory Hierarchies %R 94-23 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-24.ps.Z %A Kenneth W. Regan %T Linear Speed-Up, Information Vicinity, and Finite-State Machines %R 94-24 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-21.ps.Z %A Ashish V. Naik %A Kenneth W. Regan %A D. Sivakumar %T Quasilinear Time Complexity Theory %R 94-21 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-18.ps.Z %A Kenneth W. Regan %T Linear Time and Memory-Efficient Computation %R 94-18 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-20.ps.Z %A Lide Li %A Mitsunori Ogihara %A Kenneth W. Regan %T On Information From #P Functions %R 94-20 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-22.ps.Z %A Jin-Yi Cai %A Richard J. Lipton %A Luc Longpre %A Mitsunori Ogihara %A Kenneth W. Regan %A D. Sivakumar %T Communication Complexity of Key Agreement on Limited Ranges %R 94-22 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-26.ps.Z %A Johan M. Lammens %T A Computational Model of Color Perception and Color Naming %R 94-26 %D June 24, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-29.ps.Z %A Kenneth W. Regan %T Index Sets and Presentations of Complexity Classes (revised version) %R 94-29 %D July 29, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-30.ps.Z %A Devashis Jana %A Bharat Jayaraman %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-43.ps.Z %A Shriram Revankar %T Supervised Image Segmentation %R 93-43 %D 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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-34.ps.Z %A Yiming Gong %A Sreejit Chakravarty %T A Diagnosis Algorithm for Bridging Faults in Combinational Circuits %R 94-34 %D September 13, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-38.ps.Z %A Jin-yi Cai %A Pu Cai %A Yixin Zhu %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-28.ps.Z %A William J. Rappaport %T Understanding Understanding: Syntactic Semantics and Computational Cognition %R 94-28 %D October 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-33.ps.Z %A Krishna Moorty Sivalingam %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-27.ps.Z %A Kannan Govindarajan %A Bharat Jayaraman %A Surya Mantha %T Preference Logic Grammars %R 94-27 %D June 24, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-13.ps.Z %A Kannan Govindarajan %A Bharat Jayaraman %T Intensional AlgorithmicDebugging %R 94-13 %D May 20, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-25.ps.Z %A Wei Shu %T Runtime Incremental Parallel Scheduling (RIPS) on Distributed Memory Computers %R 94-25 %D November 11, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-32.ps.Z %A Amruth N. Kumar %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-37.ps.Z %A Devashis Jana %T Semantics of Subset-Logic Languages %R 94-37 %D November 11, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-39.ps.Z %A Ronald Sanger Curtis %T Data Structure Complexity Metrics %R 94-39 %D November 11, 1994 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-27.ps.Z %A Russ Miller %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-06.ps.Z %A Xin He %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/90-23.txt.Z %A Xin He %T An Improved Algorithm for the Planar 3-Cut Problem %R 90-23 %D February, 1990 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/90-26.txt.Z %A R. sanath %A X. He %T Efficient Parallel Algorithms for Selection and Searching on Sorted Matrices %R 90-26 %D February, 1990 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %A C.-S. Chang, G.T. DeTitta, H.A. Hauptman, R. Miller, P. Thuman, and C.M. Weeks %T Using Parallel Computers to Solve the Phase Problem of X-Ray Crystallography %R 92-15 %D 1992 (not available, final version appears in The International Journal of Supercomputer Applications, vol 7, no. 1, pp. 25-49) %I Department of Computer Science, SUNY Buffalo %K X-Ray Crystallography, Parallel Computing %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-01.ps.Z %A Aidong Zhang %A Marian Nodine %A Bharat Bhargava %T Ensuring Semi-Atomicity in Heterogeneous Distributed Database Systems %R 95-01 %D February 04, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-03.ps.Z %A Arun K. Jagota %A Giri Narasimhan %A Kenneth W. Regan %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/90-13.ps.Z %A William J. Rapaport %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %A Stuart C. Shapiro %A William J. Rapaport %T The SNePS Family %R 90-21 %D September 1990 %I Department of Computer Science, 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-02.ps.Z %A Kenneth W. Regan %A D. Sivakumar %A Jin-Yi Cai %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-08.ps.Z %A Kenneth W. Regan %A D.Sivakumar %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-07.ps.Z %A Vinay Dabholkar %A Sreejit Chakravarty %A Farid Najm %A Janak Patel %T Cyclic Stress Tests for Full Scan Circuits %R 95-07 %D February 24, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-10.ps.Z %A Marek Zaionc %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-11.dvi.Z %A Sreejit Chakravarty %A Kent Fuchs %A Janak Patel %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-15.ps.Z %A Karen Ehrlich %A William J. Rapaport %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-14.ps.Z %A B. Jayaraman and K. Moon %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-16.ps.Z %A Jin-Yi Cai %A Alan L. Selman %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-17.ps.Z %A Pu Cai %A Jin-yi Cai %A Ashish Naik %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-11.ps.Z %A Robin K. Hill %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-18.ps.Z %A Yiming Gong %A Sreejit Chakravarty %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-20.ps.Z %A Marek Zaionc %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-22.ps.Z %A Kannan Govindarajan %A Bharat Jayaraman %A Surya Mantha %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-21.ps.Z %A Rajiv Chopra %A Rohini Srihari %A Anthony Ralston %T HyperArc Consistency and Expensive Constraints %R 95-21 %D May 05, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-24.ps.Z %A Marek Zaionc %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/92-16.dvi.Z %A Sreejit Chakravarty %A Paul J. Thadikaran %T Generation and Simulation of IDDQ Tests for Bridging and Leakage Faults in Combinational Circuits %R 92-16 %D 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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-25.ps.Z %A David R. Koepsell %A William J. Rapaport %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/93-41.ps.Z %A Jin-yi Cai %A W.H.J. Fuchs %A Dexter Kozen %A Zicheng Liu %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-27.ps.Z %A Jin-yi Cai %A Zicheng Liu %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-29.ps.Z %A L. Babai %A R. Beals %A J-Y. Cai %A G. Ivanyos %A E. Luks %T Multiplicative equations over commutative matrices %R 95-29 %D July 13, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-30.ps.Z %A Jin-Yi Cai %A D. Sivakumar %T The Resolution of a Hartmanis Conjecture %R 95-30 %D July 13, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-31.ps.Z %A Jin-Yi Cai %A Ashish V. Naik %A D. Sivakumar %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-23.ps.Z %A Davin Milun %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-35.ps.Z %A Debashish Niyogi %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-12.ps.Z %A Aidong Zhang %A Biao Cheng %A Raj Acharya %T Texture-Based Image Retrival Using Fractals %R 95-12 %D July 21, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-35.ps.Z %A Jin-Yi Cai %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-36.ps.Z %A Jin-Yi Cai %T Frobenius's degree formula and Toda's polynomials %R 95-36 %D August 10, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-34.ps.Z %A Min-You Wu %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. %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-31.ps.Z %A Aidong Zhang %T Impact of Multimedia Data on Workflow %R 94-31 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/94-43.ps.Z %A Aidong Zhang %A Marian Nodine %A Bharat Bhargava %T Ensuring Semi-Atomicity in Heterogeneous Distributed Database Systems %R 94-43 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-05.ps.Z %A Aidong Zhang %A Biao Cheng %A Raj Acharya %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 %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-19.ps.Z %A Aidong Zhang %A Biao Cheng %A Raj Acharya %T Texture-Based Image Retrieval Using Fractal Codes %R 95-19 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-33.ps.Z %A Aidong Zhang %T On Synchronized Presentation Management in Multimedia Database Systems %R 95-33 %D August 16, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-37.ps.Z %A Kannan Govindarajan %A Bharat Jayaraman %A Surya Mantha %T Optimization and Relaxation in Constraint Logic Languages %R 95-37 %D August 21, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-39.ps.Z %A K.W. Regan %A H. Vollmer %T Gap Languages and Log-Time Complexity Classes %R 95-39 %D September 12, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-40.ps.Z %A Jin-Yi Cai %A D. Sivakumar %T Resolution of Hartmanis' Conjecture for NL-hard sparse sets %R 95-40 %D September 18, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-41.ps.Z %A Jin-Yi Cai %A Mitsunori Ogihara %T Sparse Sets versus Complexity Classes %R 95-41 %D September 18, 1995 %I Department of Computer Science, SUNY Buffalo %Z Tue, 19 Sep 1995 15:03:53 GMT %U http://www.cs.buffalo.edu/pub/tech-reports/95-43.ps.Z %A S. Ravikumar %A D. Sivakumar %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. %Z Thu, 21 Sep 1995 17:10:00 GMT %U http://www.cs.buffalo.edu/pub/tech-reports/95-42.ps.Z %A Jin-Yi Cai, Ashish V. Naik, D. Sivakumar %T Bounded Truth Table Reductions of P %R 95-42 %D Sept. 21, 1994 %I Department of Computer Science, SUNY Buffalo %Z Fri, 22 Sep 1995 03:00:12 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-38.ps.Z %A Giovanni Seni %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 /u5/grads/seni/abstract.tex %Z Mon, 16 Oct 1995 16:25:34 GMT %U ftp://ftp.cs.buffalo.edu/pub/tech-reports/95-45.ps.Z %A Petr Slavik %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. %Z Wed, 18 Oct 1995 13:48:31 GMT