The multi-dimensional concordance: A new tool for literary research

This paper describes the use of correspondence analysis to create the space of a book, constructs that of Kierkegaard'sFear and Trembling as an illustration, and distinguishes three separate contexts of some of its most important words: thespatial context (where the search word lies in that named and ordered space); theoverall context (the x words closest to the search word in multi-dimensional space); and the role/sense context (the words associated with the search word in each of its most important roles, some of which may represent new senses.) It describes the identification of these contexts, discusses their importance and concludes by noting certain respects in which the procedure might perhaps be improved. Alastair McKinnon is Professor Emeritus of McGill's Department of Philosophy and has just been appointed research consultant at the new Kierkegaard Research Center in Copenhagen. His most recent publications include electronic versions of Wittgenstein's Published Writingsand Kierkegaard's Dagbøger.     

3-D interpretation of optical flow by renormalization

This article studies 3-D interpretation of optical flow induced by a general camera motion relative to a surface of general shape. First, we describe, using the image sphere representation, an analytical procedure that yields an exact solution when the data are exact: we solve theepipolar equation written in terms of theessential parameters and thetwisted optical flow. Introducing a simple model of noise, we then show that the solution is statistically biased. In order to remove the statistical bias, we propose an algorithm calledrenormalization, which automatically adjusts to unknown image noise. A brief discussion is also given to thecritical surface that yields ambiguous 3-D interpretations and the use of theimage plane representation.     

Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays

Summary Linear arrays are characterized by a small communication bandwidth and a large communication diameter rendering them unsuited to the implementation of global computations. This paper presents efficient data movement and partitioning techniques to overcome several shortcomings of linear arrays. These techniques are used to derive optimal parallel algorithms for several geometric problems onn×n images using a fixed-size linear array withp processors, where 1pn.O(n ²/p) time solutions are presented for labeling connected image regions, computing the convex hull of each region, and computing nearest neighbors. Consequently, a linear array withn processors can solve several image problems inO(n) time which is the same time taken by a two dimensional mesh-connected computer withn ² processors. Limitations of linear arrays are analyzed by presenting a class of image problems which can be solved sequentially inO(n) ² ) time, but require (n ²) time on a linear array, irrespective of the number of processors used and the partitioning of the input image among the processors. An alternate communication-efficient fixed-size organization withp processors is proposed to solve such problems inO(n ²/p) time, for 1pn. Hussein M. Alnuweiri received the B.S. and M.S. degrees in 1983 and 1984, respectively, both in electrical engineering from King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia, and received the Ph.D. degree also in electrical engineering in 1989 from the University of Southern California, Los Angeles. Currently he is an assistant professor in the electrical engineering department at University of British Columbia. His research interests include parallel architectures and algorithms, computational aspects of VLSI networks, complexity of parallel computations, and algorithmic aspects of image analysis, vision, and robot motion planning. Viktor K. Prasanna (V. K. Prasanna Kumar) received his BS in Electronics Engineering from the Bangalore University, his MS from the School of Automation, Indian Institute of Science. He obtained his Ph.D. in Computer Science from Pennsylvania State University in 1983. Currently, he is an Associate Professor in the department of Electrical Engineering-Systems, University of Southern California, Los Angeles. His current research interests include Parallel Computation, Computer Architecture, VLSI Computations and Computational aspects of Image Processing and Vision. He is the editor of the book Parallel Architectures and Algorithms for Image understanding published by Academic Press. Professor Prasanna serves on number of international committees and panels and is a consultant for several industries. He is the program chair of the 1992 International Parallel Processing Symposium sponsored by IEEE Computer Society and is a subject area editor of Journal of Parallel and Distributed Computing.This research was supported in part by the National Science Foundation under grant IRI-8710836 and in part by DARPA under contract F 33615-87-C-1436 monitored by Wright Patterson Airforce Base. A preliminary version of this paper appears in the IEEE Conference on Computer Vision and Pattern Recognition, 1988.     

Pseudo-Additive Measures and Triangular-Norm-Based Conditioning

Conditioning in the framework of fuzzy measures (monotone normalized set functions vanishing in the empty set) is introduced. For every set B with non-null measure m(B) a conditional measure m _B , based on a triangular norm T, is introduced. Universal conditioning preserving the lower semi-continuity is shown to be necessarily based on some strict triangular norm. Then also each conditional measure m _B related to a pseudo-additive measure m is pseudo-additive. However, the pseudo-addition _B operating on the measures m _B is in general different from the pseudo-addition operating on the measure m. Specific cases of universal conditioning preserving the pseudo-addition are characterized. Classical probabilistic conditioning is shown to be a special case.     

P-selective sets,tally languages,and the behavior of polynomial time reducibilities onNP

The notion ofp-selective sets, and tally languages, are used to study polynomial time reducibilities onNP. P-selectivity has the property that a setA belongs to the classP if and only if both _m ^p A andA isp-selective. We prove that for every tally language set inNP there exists a polynomial time equivalent set inNP that isp-selective. From this result it follows that if NEXT DEXT, then polynomial time Turing and many-one reducibilities differ onNP. This research was supported in part by the National Science Foundation under grant MCS 77-23493     

General circular permutation layout

In thegeneral circular permutation layout problem there are two concentric circles,C _in andC _out. There are a set ofn inner terminals onC _in and a set ofn outer terminals onC _out: terminalsi onC _in and _i onC _out are to be connected by means of a wire, where 1 i n. All wires must be realized in the interior ofC _out. Each wire can intersectC _in at most once and at mostK wires, for a fixedK, can pass between two adjacent inner terminals. A linear-time algorithm for obtaining a planar homotopy (single-layer realization) of an arbitrary instance of the general circular permutation layout problem, forK 0, is proposed. Previously,K = 1 has been studied. In this paper the algorithm is also extended to a more general problem, in which the number of wires allowed to pass between each pair of adjacent terminals onC _in may be different from pair to pair.The work of R. D. Lou and M. Sarrafzadeh was supported in part by the National Science Foundation under Grants MIP-8709074 and MIP-8921540. C. S. Rim, K. Nakajima, and S. Masuda's work was supported in part by the National Science Foundation under Grants MIP-8451510 and CDR-8803012 (Engineering Research Centers Program), and a grant from AT&T.     

Three ∑ P 2 -complete problems in computational learning theory

The consistency problem associated with a concept classC is to determine, given two setsA andB of examples, whether there exists a conceptc inC such that eachx inA is a positive example ofc and eachy inB is a negative example ofc. We explore in this paper the following intuition: for a concept classC, if the membership problem of determining whether a given example is positive for a concept isNP-complete, then the corresponding consistency problem is likely to be _P ² -complete. To support this intuition, we prove that the following three consistency problems for concept classes of patterns, graphs and generalized Boolean formulas, whose membership problems are known to beNP-complete, are _P ² -complete: (a) given two setsA andB of strings, determine whether there exists a patternp such that every string inA is in the languageL(p) and every string inB is not in the languageL(p); (b) given two setsA andB of graphs, determine whether there exists a graphG such that every graph inA is isomorphic to a subgraph ofG and every graph inB is not isomorphic to any subgraph ofG; and (c) given two setsA andB of Boolean formulas, determine whether there exists a 3-CNF Boolean formula such that for every A, is satisfiable and for every B, is not satisfiable. These results suggest that consistendy problems in machine learning are natural candidates for _P ² -complete problems if the corresponding membership problems are known to beNP-complete.In addition, we prove that the corresponding prediction problems for concept classes of polynomial-time nondeterministic Turing machines, nondeterministic Boolean circuits, generalized Boolean formulas, patterns and graphs are prediction-complete for the classR _NP of all concept classes whose membership problems are inNP.     

A project for Latin Lexicography: 2. A Latin morphological analyzer

This article describes a second aspect of the Project for Latin Lexicography (see previous article). We here concentrate on two aspects of the project. First, we describe the morphological analyzer, which comprises a base dictionary, a table of suffixes, a table of endings and a table of postfixes. Second, we describe the lemmatization module, which operates by reference to a series of grammatical codes or information given for the base, and reference codes. Giuseppe Cappelli is a program analyst working at the Institute for Computational Linguistics of the National Research Council of Pisa. He has written the software for the morphosyntactic analyzer of the Spanish language. He has also written the software for the morphological analyser of the Latin language in collaboration with the Classics Department of Turin University. At present, Cappelli is involved in the study of child language. His publications include (with M.N. Catarsi, A. Saba and D. Ratti) A Morphosyntactic analyser for Spanish, Computers in Literary and Linguistic Research, Pisa: Giardini Editori, 1982; and (with A. Bozzi) A Latin Morphological Analyser, in Data Base Oriented Source Editions, Kalamazoo, Michigan, 1988. Andrea Bozzi is a researcher at the Institute for Computational Linguistics of the National Research Council of Pisa. She has been involved in the automatic processing of late Latin translations of Hypocratical texts, from a lexicographical point of view. She has also implemented a morphological analyzer of the Latin language. Her publications include Note di lessicografia ippocratica. Il trattato sulle arie, le acque, i luoghi, Roma, 1982, and Il trattamento delle variante nello spoglio elttronico di un testo. Una prova sui Carmina di Claudiano, in MD, 16 (1986),155–79.     

Computer enhanced assessment of case-notes in studies of psychopathology: The example of an autistic subject

Case report notes on encounters and exchanges between a clinician and a patient are a rich and irreplaceable source of information in studies of psychopathology. The analysis and exploitation of these notes may be considerably enhanced by transcribing the original notes to computer text files, and subsequently submitting these files to computerized reading. This makes it possible to take account both of qualitative and quantitative features of the behaviour and events described in the notes. Notes taken during encounters with an autistic subject were analyzed in this way. The subject's verbal and gestural repertoires were identified, together with their relative frequencies, their principal associations, and their trends over successive encounters for the items described. The method also made it possible to specify the way in which the Observer was involved in encounters, and his role in them. Major conclusions were that the autistic subject distinctly avoided triadic situations, preferentially pronounced words and phonemes similar to those of his own name, and did not distinguish between the representations he had of persons, objects, places, gestures and words. He also failed to distinguish between the representation he had of himself and of his own name.J.-M. Vidal (Docteur d'Etat, 1976) is Chargé de Recherche CNRS. He studied the behavioral process of attachment in animals before studying discontinuities of mind between animals and humans, and psychopathological processes of non-attachment in autistic subjects. He has published, Motivation et attachement, inEncyclopédie de la Pléiade, Paris: Gallimard, 1987, and Evolution des psychismes et évolution des organismes, inDarwinisme et Société, Paris: Presses Universitaires de France, 1992. R. Quris is Ingénieur de Recherche CNRS. He specializes in the application of linear algebraic models in multivariate analysis which he originally applied to behavioral data from animals. More recently, he extended these applications, with his ANATEXT program, to the analysis of lexical data drawn from clinical dialogues. He is also the author of other multivariate analysis programs:Calmat Matrix Computation Tool, v. 1.4 (1993), Exeter Software, 100 North Country Road, Setauket, NY 11733, andGTABM, gestionnaire de tableaux multiples, v. 2.0 (1994), CNRS 74E, rue de Paris, 3069 Rennes, France.     

A theory of nonmonotonic rule systems I

We introduce here the study of generalnonmonotonic rule systems. These deal with situations where a conclusion is drawn from a system of beliefsS (and seen to be inS), basedboth on some premises being inS and on some restraints not being inS. In the monotone systems of traditional logic there are no restraints, conclusions are drawn solely based on premises being inS. Nonmonotonic rule systems capture the essential syntactic, semantic, and algorithmic features of many nonmonotone systems such as default logic, negation as failure, truth maintenance, autoepistemic logic, and also important combinatorial questions from mathematics such as the marriage problem. This reveals semantics and syntax and proof procedures and algorithms for computing belief sets in many cases where none were previously available and entirely uniformly. In particular, we introduce and study deductively closed sets, extensions and weak extensions. Semantics of nonmonotonic rule systems is studied in part II of this paper and extensions to predicate classical, intuitionistic, and modal logics are left to a later paper.Work partially supported by NSF grant RII-8610671 and Kentucky EPSCoR program and ARO contract DAAL03-89-K-0124.Work partially supported by NSF grant DMS-8902797 and ARO contract DAAG629-85-C-0018.Work partially supported by NSF grant DMS-8702473.     

Parallel complexity of logical query programs

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the polynomial fringe property, this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the linear and piecewise linear classes of logic programs are inN C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an elementary chain. We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the polynomial fringe property; hence such programs are inN C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.Supported by NSF Grant IST-84-12791, a grant of IBM Corporation, and ONR contract N00014-85-C-0731.     

The Kreisel length-of-proof problem

A first-order system F has theKreisel length-of-proof property if the following statement is true for all formulas(x): If there is ak1 such that for alln0 there is a proof of(¯n) in F with at mostk lines, then there is a proof of x(x) in F. We consider this property for Parikh systems, which are first-order axiomatic systems that contain a finite number of axiom schemata (including individual axioms) and a finite number of rules of inference. We prove that any usual Parikh system formulation of Peano arithmetic has the Kreisel length-of-proof property if the underlying logic of the system is formulated without a schema for universal instantiation in either one of two ways. (In one way, the formula to be instantiated is built up in steps, and in the other way, the term to be substituted is built up in steps.) Our method of proof uses techniques and ideas from unification theory.     

Reduced-order controllers inH ∞-Optimal synthesis methods of the first kind

It has often been believed that inH -optimal synthesis methods, the resulting controllers have order much greater than the order of the plant. Recently, Limebeer and Hung [9] have shown that inH -optimal synthesis problems of the first kind both optimal as well as suboptimal controllers have order which is no greater than the order of the plant. However, those authors do not provide any explicit algorithm for computing these controllers. In this paper we derive an explicit procedure for computing suboptimal controllers in problems of the first kind. These controllers have order no greater than the order of the plant and can be computed by solving only two Riccati and two Lyapunov equations.This research was supported by the National Science Foundation under Grant No. ECS-8810-578.     

The century of prose corpus: A half-million word historical data base

The Century of Prose Corpus is a historical corpus of British English of the period 1680–1780. It has been designed to provide a resource for students of the language of that era. The COPC is diachronic and may be considered a unit in what will eventually become a series of corpora providing access to the whole of the English language from the oldest specimens to the present. This article describes and explains the various features of the COPC.Louis T. Milic is Professor of English Emeritus at Cleveland State University. He retired from teaching in 1991 and has been Secretary-Treasurer of the Dictionary Society of North America since 1990. He has also occupied himself with research and publication: Zeugmas in Gibbon's History,Prose Studies (1991), Fielding's Linguistic Sub-Stratum,Orbis Litterarum (1990).     

Authorship attribution

This paper considers the problem of quantifying literary style and looks at several variables which may be used as stylistic fingerprints of a writer. A review of work done on the statistical analysis of change over time in literary style is then presented, followed by a look at a specific application area, the authorship of Biblical texts.David Holmes is a Principal Lecturer in Statistics at the University of the West of England, Bristol with specific responsibility for co-ordinating the research programmes in the Department of Mathematical Sciences. He has taught literary style analysis to humanities students since 1983 and has published articles on the statistical analysis of literary style in theJournal of the Royal Statistical Society, History and Computing, andLiterary and Linguistic Computing. He presented papers at the ACH/ALLC conferences in 1991 and 1993.     

On the VC Dimension of Bounded Margin Classifiers

In this paper we prove a result that is fundamental to the generalization properties of Vapnik's support vector machines and other large margin classifiers. In particular, we prove that the minimum margin over all dichotomies of k n + 1 points inside a unit ball in R ⁿ is maximized when the points form a regular simplex on the unit sphere. We also provide an alternative proof directly in the framework of level fat shattering.     

The plane with parallel coordinates

By means ofParallel Coordinates planar graphs of multivariate relations are obtained. Certain properties of the relationship correspond tothe geometrical properties of its graph. On the plane a point line duality with several interesting properties is induced. A new duality betweenbounded and unbounded convex sets and hstars (a generalization of hyperbolas) and between Convex Unions and Intersections is found. This motivates some efficient Convexity algorithms and other results inComputational Geometry. There is also a suprising cusp inflection point duality. The narrative ends with a preview of the corresponding results inR ^N .     

A faster parametric minimum-cut algorithm

Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek maximum flows and minimum cuts can be computed simply in O(n³+kn²) total time, provided that the capacity changes are made in order. Using dynamic trees their time bound isO(nm log(n²/m)+km log(n²/m)). We show how to reduce the total time, using a simple algorithm, to O(n³+kn) for explicitly computing thek minimum cuts and implicitly representing thek flows. Using dynamic trees our bound is O(nm log(n²/m)+kn log(n²/m)). We further reduce the total time toO(n ²m) ifk is at most O(n). We also apply the ideas from [10] to show that the faster bounds hold even when the capacity changes are not in order, provided we only need the minimum cuts; if the flows are required then the times are respectively O(n³+km) and O(n²m). We illustrate the utility of these results by applying them to therectilinear layout problem.The research of Dan Gusfield was partially supported by Grants CCR-8803704 and CCR-9103937 from the National Science Foundation. The research of Éva Tardos was partially supported by a David and Lucile Packard Fellowship, an NSF Presidential Young Investigator Fellowship, a Research Fellowship of the Sloan Foundation, and by NSF, DARPA, and ONR through Grant DMS89-20550 from the National Science Foundation.     

A data structure for arc insertion and regular path finding

Let be the language defined by some deterministick-state automaton with accepting statesF, and letG be a directed graph withn nodes andm labeled arcs. Thedynamic -path problem is to process efficiently and on-line two kinds of operations: (1) inserting arcs intoG, and (2) given two nodesu andv inG, finding a path fromu tov that is labeled by some word of , or reporting that none exists. We present a data structure that supports insertion and regular path existence queries inO(nk ²) amortized time andO(|F|) worst-case time, respectively. Deletions only (no insertions) can also be accommodated in directed acyclic graphs. Finding an -path between two nodes can be done inO(l+|F|) worst-case time, wherel is the length of the path returned. This is an improvement over theO(m) time required to answer queries in the static version of this problem, for each fixed infinite . We show how this data structure and the techniques used for building it are applicable to the area of knowledge base querying. In an amortized setting, we provide relative improvements ofO(m/n) to the time bounds for answering many one-sided recursive queries and even some two-sided recursive queries, such as the same generation query on acyclic graphs.An extended abstract of this paper was presented at the first annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 1990.Work partially completed while at Brown University. Work at Princeton partially supported by the NSF Center in Discrete Mathematics and Theoretical Computer Science (DIMACS).Work supported in part by NSF grant IRI-8617344, by an Alfred P. Sloan Foundation Fellowship, and by ONR grant N00014-83-K-0146, ARPA Order No. 4786.Work supported in part by an NSF Presidential Young Investigator Award with matching funds from IBM, by NSF research grant DCR-8403613, and by ONR grant N00014-83-K-0146, ARPA Order No. 4786.     

OnP-subset structures

Given a setA, we investigate the lattice structure formed by those of its subsets that belong to the complexity classP, taken modulo finite variations and ordered by inclusion. We show that up to isomorphism, only three structures are possible for this lattice. IfA isP-immune, itsP-subset structure degenerates to the trivial one-element lattice. IfA is almostP-immune but notP-immune (for instance, ifA is inP), itsP-subset structure is isomorphic to the countable atomless Boolean lattice. In all other cases theP-subset structure is isomorphic to ⁽⁾ , the weak countable power of. All natural intractable sets appear to fall in the third category. The results generalize to many other complexity classes, and similar characterizations hold for, e.g., the structures formed by recursive complexity cores.This research was supported in part by the Emil Aaltonen Foundation, the Academy of Finland, and the National Science Foundation under Grant No. MCS83-14272. Part of the work was carried out while the second author was visiting the Department of Mathematics, University of California at Santa Barbara.