Graphical Tools and Techniques for Querying Document Databases - Sauvola,J.; David Doermann; Kauniskangas,H.; Shin,C.; Koivusaari,M.; Pietikainen,M. (BSDIA, 1997)

Hardness of flip-cut problems from optical mapping - DANČÍK,V.; Hannenhalli, Sridhar; Muthukrishnan,S. (Journal of Computational Biology, 1997)

Hardness of flip-cut problems from optical mapping [DNA molecules application] - Dancik,V.; Hannenhalli, Sridhar; Muthukrishnan,S. (Compression and Complexity of Sequences 1997. Proceedings, 1997)
Optical mapping is a new technology for constructing restriction maps. Associated computational problems include aligning multiple partial restriction maps into a single “consensus” restriction map, and determining the correct orientation of each molecule, which was formalized as the exclusive binary flip cut (EBFC) problem by Muthukrishnan and Parida (see Proc. of the First ACM Conference on Computational Molecular Biology (RECOMB), Santa Fe, p.209-19, 1997). Here, the authors prove that the EBFC problem, as well as a number of its variants, are NP-complete. They also identify another problem formalized as binary shift cut (BSC) problem motivated by the fact that there might be missing fragments at the beginnings and/or the ends of the molecules, and prove it to be NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P=NP
Keywords: binary shift cut; Biochemistry; Bioinformatics; biological techniques; Biology; biomedical optical imaging; combinatorial mathematics; combinatorial problem; computational complexity; computational problems; DNA; DNA molecule; exclusive binary flip cut; flip-cut problem hardness; Genetic engineering; Genomics; MATHEMATICS; molecular biology; molecular biophysics; molecule orientation; multiple partial restriction maps; NP-complete problem; optical mapping; polynomial time solutions; Polynomials; sequences

Image Indexing with Minimum Adaptive Spatial Segmentation - Zhong,S.; David Doermann; Rosenfeld, A. (Proceedings of VISUAL 1997, 1997)

Integrated Segmentation and Clustering for Enhanced Compression of Document Images - Kia,Omid E; David Doermann (ICDAR, 1997)

KidPad: a design collaboration between children, technologists, and educators - Druin, Allison; Stewart,J.; Proft,D.; Bederson, Benjamin B.; Hollan,J. (Proceedings of the SIGCHI conference on Human factors in computing systems, 1997)

Large-scale acquisition of LCS-based lexicons for foreign language tutoring - Dorr, Bonnie J (Proceedings of the fifth conference on Applied natural language processing, 1997)
We focus on the problem of building large repositories of lexical conceptual structure (LCS) representations for verbs in multiple languages. One of the man results of this work is the definition of a relation between broad semantic classes and LCS meaning components. Our acquisition program---LEXICALL---takes, as input, the result of previous work on verb classification and thematic grid tagging, and outputs LCS representations for different languages. These representations have been ported into English. Arabic and Spanish lexicons, each containing approximately 9000 verbs. We are currently using these lexicons in an operational foreign language tutoring and machine translation.

Large-Scale Dictionary Construction for Foreign Language Tutoring and Interlingual Machine Translation - Dorr, Bonnie J (Machine Translation, 1997)
This paper describes techniques for automatic construction of dictionaries for use in large-scale foreign language tutoring (FLT) and interlingual machine translation (MT) systems. The dictionaries are based on a language-independent representation called “lexical conceptual structure” (LCS). A primary goal of the LCS research is to demonstrate that synonymous verb senses share distributional patterns. We show how the syntax–semantics relation can be used to develop a lexical acquisition approach that contributes both toward the enrichment of existing online resources and toward the development of lexicons containing more complete information than is provided in any of these resources alone. We start by describing the structure of the LCS and showing how this representation is used in FLT and MT. We then focus on the problem of building LCS dictionaries for large-scale FLT and MT. First, we describe authoring tools for manual and semi-automatic construction of LCS dictionaries; we then present a more sophisticated approach that uses linguistic techniques for building word definitions automatically. These techniques have been implemented as part of a set of lexicon-development tools used in the milt FLT project.

LCS-based Korean Parsing and Translation - Dorr, Bonnie J (Ms. Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, 1997)
This document reports on research conducted at the University ofMaryland for the Korean/English Machine Translation (MT) project. Our primary objective was to develop an interlingual representation based on lexical conceptual structure (LCS) and to examine the relation between this representation and a set of linguistically motivated semantic classes. We have focused on several different areas, including syntactic and morphological analysis, development of a semantic lexicon, semantic analysis of military messages, and regularization of an existing Korean military message corpus.

LEXICALL: Lexicon Construction for Foreign Language Tutoring - Dorr, Bonnie J (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1997)
We focus on the problem of building large repositories of lexical conceptual structure (LCS) representations for verbs in multiple languages. One of the main results of this work is the definition of a relation between broad semantic classes and LCS meaning components. Our acquisition program LEXICALL takes, as input, the result of previous work on verb classification and thematic grid tagging, and outputs LCS representations for different languages. These representations have been ported into English, Arabic and Spanish lexicons, each containing approximately 9000 verbs. We are currently using these lexicons in an operational foreign language tutoring and machine translation.
Keywords: *DATA ACQUISITION; *FOREIGN LANGUAGES; *MACHINE TRANSLATION; GRIDS; INFORMATION SCIENCE; LEXICOGRAPHY; LEXICONS; linguistics; Vocabulary

Local correspondence for detecting random forgeries - Guo,J. K; David Doermann; Rosenfeld, A. (Document Analysis and Recognition, 1997., Proceedings of the Fourth International Conference on, 1997)
Progress on the problem of signature verification has advanced more rapidly in online applications than offline applications, in part because information which can easily be recorded in online environments, such as pen position and velocity, is lost in static offline data. In offline applications, valuable information which can be used to discriminate between genuine and forged signatures is embedded at the stroke level. We present an approach to segmenting strokes into stylistically meaningful segments and establish a local correspondence between a questioned signature and a reference signature to enable the analysis and comparison of stroke features. Questioned signatures which do not conform to the reference signature are identified as random forgeries. Most simple forgeries can also be identified, as they do not conform to the reference signature's invariant properties such as connections between letters. Since we have access to both local and global information, our approach also shows promise for extension to the identification of skilled forgeries
Keywords: applications; online; applications; questioned; correspondence; offline; detection; reference; extraction; handwriting; features; stroke; forged; forgeries; random; forgeries; stroke; Forgery; level; stroke; meaningful; processing; properties; local; recognition; image; segmentation; stylistically; segmentation; word; segments; feature; signature; random; signature; signature; signatures; invariant; verification; skilled

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model - Agarwala,Richa; Batzoglou,Serafim; DančíK,Vlado; Decatur,Scott E.; Hannenhalli, Sridhar; Farach,Martin; Muthukrishnan,S.; Skiena,Steven (Journal of Computational Biology, 1997)
We consider the problem of determining the three-dimensional folding of a protein given its one-dimensional amino acid sequence. We use the HP model for protein folding proposed by Dill (1985), which models protein as a chain of amino acid residues that are either hydrophobic or polar, and hydrophobic interactions are the dominant initial driving force for the protein folding. Hart and Istrail (1996a) gave approximation algorithms for folding proteins on the cubic lattice under the HP model. In this paper, we examine the choice of a lattice by considering its algorithmic and geometric implications and argue that the triangular lattice is a more reasonable choice. We present a set of folding rules for a triangular lattice and analyze the approximation ratio they achieve. In addition, we introduce a generalization of the HP model to account for residues having different levels of hydrophobicity. After describing the biological foundation for this generalization, we show that in the new model we are able to achieve similar constant factor approximation guarantees on the triangular lattice as were achieved in the standard HP model. While the structures derived from our folding rules are probably still far from biological reality, we hope that having a set of folding rules with different properties will yield more interesting folds when combined.

Locally adaptive document skew detection - Sauvola,Jaakko J; David Doermann; Pietikaeinen,Matti (Proceedings of SPIE, 1997)
This paper proposes a new approach to the detection of local orientation and skew in document images. It is based on the observation that there are many documents where a single global estimate of the page skew is not sufficient. These documents require local adaptation to deal robustly with todays complex configurations of components on the page. The approach attempts to identify regions in the image which exhibit locally consistent physical properties and consistent physical properties and consistent orientation. To do this, we rapidly compute a coarse segmentation and delineate regions which differ with respect to layout and/or physical content. Each region is classified as text, graphics, mixed text/graphics, image or background using local features and additional features are extracted to estimate orientation. The local orientation decisions are propagated where appropriate to resolve ambiguity and to produce a global estimate of the skew for the page. The implementation of our algorithms is demonstrated on a set of images which have multiple regions with different orientations.

Multiscale Document Page Segmentation Using Soft Decision Integration - Etemad,K.; David Doermann; Chellapa, Rama (IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997)

Navigating static environments using image-space simplification and morphing - Darsa,Lucia; Costa Silva,Bruno; Varshney, Amitabh (Proceedings of the 1997 symposium on Interactive 3D graphics, 1997)

OCR-based rate-distortion analysis of residual coding - Kia,O. E; David Doermann (Image Processing, 1997. Proceedings., International Conference on, 1997)
Symbolic compression of document images provides access to symbols found in document images and exploits the redundancy found within them. Document images are highly structured and contain large numbers of repetitive symbols. We have shown that while symbolically compressing a document image we are able to perform compressed-domain processing. Symbolic compression forms representative prototypes for symbols and encode the image by the location of these prototypes and a residual (the difference between symbol and prototype). We analyze the rate-distortion tradeoff by varying the amount of residual used in compression for both distance- and row-order coding. A measure of distortion is based on the performance of an OCR system on the resulting image. The University of Washington document database images, ground truth, and OCR evaluation software are used for experiments
Keywords: analysis; redundancy; representative; character; coding; distortion; coding; image; coding; lossy; coding; row-order; coding; symbolic; compression; data; compression; document; compression; lossy; database; distortion; Evaluation; image; images; document; images; experiments; ground; measure; document; OCR; of; performance; University; processing; distance-order; processing; image; prototypes; residual; recognition; rate; representation; optical; representation; progressive; software; OCR; system; theory; transmission; rate-distortion; truth; image; Washington; compressed-domain

Parallelizing and algorithm for visibility on polyhedral terrain - Teng,Y. A; Mount, Dave; Puppo,E.; Davis, Larry S. (International Journal of Computational Geometry and Applications, 1997)
The best known output-sensitive sequential algorithm for computing the viewshedon a polyhedral terrain from a given viewpoint was proposed by Katz, Overmars, and Sharir 10, and achieves time complexity O((k + n(n)) logn) where n and k are the input and output sizes respectively, and () is the inverse Ackermann's function. In this paper, we present a parallel algorithm that is based on the work mentioned above, and achieves O(log2 n) time complexity, with work complexity O((k +n(n)) logn) in a CREW PRAM model. This improves on previous parallel complexity while maintaining work e ciency with respect to the best sequential complexity known.

Probabilistic verification of a synchronous round-based consensus protocol - Duggal,H.S.; Michel Cukier; Sanders,W. H. (1997)
Consensus protocols are used in a variety of reliable distributed systems, including both safety-critical and business-critical applications. The correctness of a consensus protocol is usually shown, by making assumptions about the environment in which it executes, and then proving properties about the protocol. But proofs about a protocol's behavior are only as good as the assumptions which were made to obtain them, and violation of these assumptions can lead to unpredicted and serious consequences. We present a new approach for the probabilistic verification of synchronous round based consensus protocols. In doing so, we make stochastic assumptions about the environment in which a protocol operates, and derive probabilities of proper and non proper behavior. We thus can account for the violation of assumptions made in traditional proof techniques. To obtain the desired probabilities, the approach enumerates possible states that can be reached during an execution of the protocol, and computes the probability of achieving the desired properties for a given fault and network environment. We illustrate the use of this approach via the evaluation of a simple consensus protocol operating under a realistic environment which includes performance, omission, and crash failures
Keywords: business-critical applications; consensus protocol correctness; crash failures; formal verification; network environment; probabilistic verification; probabilities; probability; program verification; proper behavior; protocol behavior; Protocols; realistic environment; reliable distributed systems; safety-critical applications; simple consensus protocol; software reliability; stochastic assumptions; synchronous round based consensus protocol; synchronous round based consensus protocols; traditional proof techniques

Query previews for networked information systems: a case study with NASA environmental data - Doan,K.; Plaisant, Catherine; Shneiderman, Ben; Bruns,T. (SIGMOD Record, 1997)
Formulating queries on networked information systemsis laden with problems: data diversity, data complexity, network growth, varied user base, and slow network access. This paper proposes a new approach to a network query user interface which consists of two phases: query preview and query refinement. This new approach is based on dynamic queries and tight coupling, guiding users to rapidly and dynamically eliminate undesired items, reduce the data volume to a manageable size, and refine queries locally before submission over a network. A two-phase dynamic query system for NASA’s Earth Observing Systems--Data Information Systems (EOSDIS) is presented. The prototype was well received by the team of scientists who evaluated the interface.

Query previews in networked information systems: the case of EOSDIS - Plaisant, Catherine; Bruns,Tom; Shneiderman, Ben; Doan,Khoa (CHI '97 extended abstracts on Human factors in computing systems: looking to the future, 1997)
Dynamic queries have been shown to be an effective technique to browse information, and to find patterns and exceptions. Dynamic queries involve the interactive control by a user of visual query parameters that generate rapid (100 ms update), animated, and visual displays of database search results. The data of early implementations was stored in local memory to guarantee optimal speed. Problems arise when the data is very large and distributed over a network. To overcome the problems of slow networks and data volume we propose a two-phase approach to query formulation using query previews and query refinements [1]. Preview mechanisms have been used in the past [2] and we believe that their use will be a major component of successful networked information systems interfaces (e.g. [3]).
Keywords: direct manipulation; dynamic query; earth science; network information system; query preview; Visualization

The Retrieval of Document Images: ABrief Survey - David Doermann (ICDAR, 1997)

The role of compressed document images in transmission and retrieval - Kia,O.; David Doermann (Multimedia Signal Processing, 1997., IEEE First Workshop on, 1997)
Document images belong to a unique class of images where the information content is contained in the language represented by a series of symbols on the page, rather than in the visual objects themselves. For this reason, it is essential to preserve the fidelity of individual components when considering methods of compression. Likewise the component level structure should be a prime consideration when ordering information for lossy or progressive transmission. We refine our work on document image compression as it applies to transmission and retrieval. We first overview the basic compression scheme, then describe a structural hierarchy which provides desirable properties for transmission. We present the results of a rate distortion experiment and discuss the implications for network applications
Keywords: applications; progressive; coding; multimedia; component; compression; document; compression; image; computing; query; content; lossy; databases; distortion; experiment; structural; hierarchy; symbols; visual; image; level; objects; data; processing; image; processing; visual; retrieval; image; structure; document; transmission; information; transmission; multimedia; network; transmission; rate

Spanish EuroWordNet and LCS-Based Interlingual MT - Dorr, Bonnie J; Marti,M. Antonia; Castellon,Irene (IN PROCEEDINGS OF THE MT SUMMIT WORKSHOP ON INTERLINGUAS IN MT, 1997)
We present a machine translation framework in which the interlingua -- Lexical Conceptual Structure (LCS) -- is coupled with a definitional component that includes bilingual (EuroWordNet) links between words in the source and target languages. While the links between individual words are language-specific, the LCS is designed to be a language-independent, compositional representation. We take the view that the two types of information -- shallower, transfer-like knowledge as well as deeper, compositional knowledge -- can be reconciled in interlingual machine translation, the former for overcoming the intractability of LCS-based lexical selection, and the latter for relating the underlying semantics of two words cross-linguistically. We describe the acquisition process for these two information types and present results of hand-verification of the acquired lexicon. Finally, we demonstrate the utility of the two information types in interlingual MT.

A survey of the Trypanosoma brucei rhodesiense genome using shotgun sequencing - El‐Sayed, Najib M.; Donelson,John E. (Molecular and Biochemical Parasitology, 1997)
A comparison of the efficiency of sequencing random genomic DNA fragments versus random cDNAs for the discovery of new genes in African trypanosomes was undertaken. Trypanosome DNA was sheared to a 1.5-2.5 kb size distribution, cloned into a plasmid and the sequences at both ends of 183 cloned fragments determined. Sequences of both kinetoplast and nuclear DNA were identified. New coding regions were discovered for a variety of proteins, including cell division proteins, an RNA-binding protein and a homologue of the Leishmania surface protease GP63. In some cases, each end of a fragment was found to contain a different gene, demonstrating the proximity of those genes and suggesting that the density of genes in the African trypanosome genome is quite high. Repetitive sequence elements found included telomeric hexamer repeats, 76 bp repeats associated with VSG gene expression sites, 177 bp satellite repeats in minichromosomes and the Ingi transposon-like elements. In contrast to cDNA sequencing, no ribosomal protein genes were detected. For the sake of comparison, the sequences of 190 expressed sequence tags (ESTs) were also determined, and a similar number of new trypanosomal homologues were found including homologues of another putative surface protein and a human leucine-rich repeat-containing protein. We conclude from this analysis and our previous work that sequencing random DNA fragments in African trypanosomes is as efficient for gene discovery as is sequencing random cDNA clones.
Keywords: Expressed sequence tag; Genome survey sequence; Trypanosoma brucei rhodesiense

Symbolic Compression and Processing of Document Images - Kia,Omid; David Doermann; Rosenfeld,Azriel; Chellapa, Rama (University of Maryland, College Park, 1997)
In this paper we describe a compression and representation scheme which exploits the component-level redundancy found within a document image. The approach identifies patterns which appear repeatedly, represents similar patterns with a single prototype, stores the location of pattern instances and codes the residuals between the prototypes and the pattern instances. Using a novel encoding scheme, we provide a representation which facilitates scalable lossy compression and progressive transmission, and supports document image analysis in the compressed domain. We motivate the approach, provide details of the encoding procedures, report compression results and describe a class of document image understanding tasks which operate on the compressed representation.

Techniques for Automated Testing for Automated Testing of Document Analysis Algorithms - Sauvola,J.; Kauniskangas,H.; David Doermann; Pietikainen,M. (Proceedings of the First Brazilian Symposium on Document Image Analysis, 1997)

Temporal Multi-scale Models for Image Motion Estimation - Yacoob,Yaser; Davis, Larry S. (Image Understanding Workshop: proceedings of a workshop held in New Orleans, Louisiana, May 11-14, 1997, 1997)

Toward Compact Monotonically Compositional Interlingua Using Lexical Aspect - Dorr, Bonnie J; Olsen,Mari B; Thomas,Scott C (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1997)
We describe a theoretical investigation into the semantic space described by our interlingua (IL), which currently has 191 main verb classes divided into 434 subclasses. represented by 237 distinct Lexical Conceptual Structures (LCSs). Using the model of aspect in Olsen (1994b, 1997a) monotonic aspectual composition we have identified 71 aspectually basic subclasses that are associated with one or more of 68 aspectually non-basic classes via some lexical ("type-shifting") rule (Bresnan 1982, Pinker 1984, Levin and Rappaport Hovav 1995). This allows us to refine the IL and address certain computational and theoretical issues at the same time. From a linguistic viewpoint, the expected benefits include a refinement of the aspectual model in (Olsen :1994b, 1997a) (which provides necessary but not sufficient conditions for aspectual composition), and a refinement of the verb classifications in (Levin 1993); we also expect our approach to eventually produce a systematic definition (in terms of LCSs and compositional operations) of the precise meaning components responsible for Levin's classification. Computationally, the lexicon is made more compact.
Keywords: *LEXICOGRAPHY; *SEMANTICS; COMPOSITION(PROPERTY); linguistics; MODELS; STRUCTURES; THEORY; Vocabulary

Using WordNet to Posit Hierarchical Structure in Levin's Verb Classes - Olsen,M.B.; Dorr, Bonnie J; Clark,D.J. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1997)
In this paper we report on experiments using WordNet synset tags to evaluate the seman-tic properties of the verb classes cataloged by Levin 1993. This paper represents ongoing research begun at the University of Pennsylvania (Rosenzweig et al. 1997, Palmer et al. 1997) and the University of Maryland (Dorr and Jones 1996b, 1996d, 1996e). Using WordNet sense tags to constrain the intersection of Levin classes, we avoid spurious class intersections introduced by homonymy and polysemy (run a bath, run a mile). By adding class intersections based on a single shared sense-tagged word, we minimize the impact of the non-exhaustiveness of Levin's database (Dorr and Olsen 1996, Dorr to appear). By examining the syntactic properties of the intersective classes, we provide a clearer picture of the relationship between WordNet/EuroWordNet and the LCS interlingua for machine translation and other NLP applications.

The vegetation canopy lidar mission - Dubayah, R.; Blair,J. B.; Bufton,J. L.; Clark,D. B.; JaJa, Joseph F.; Knox,R.; Luthcke,S. B.; Prince,S.; Weishampel,J. (Proceedings of Land Satellite Information in the Next Decade, II: Sources and Applications. Bethesda (MD): American Society of Photogrammetry and Remote Sensing, 1997)
The Vegetation Canopy Lidar (VCL) is the first selected mission of NASA’s new EarthSystem Science Pathfinder program. The principal goal of VCL is the characterization of the three-dimensional structure of the earth; in particular, canopy vertical and horizontal structure and land surface topography. Its primary science objectives are: landcover characterization for terrestrial ecosystem modeling, monitoring and prediction; landcover characterization for climate modeling and prediction; and, production of a global reference data set of topographic spot heights and transects. VCL will provide unique data sets for understanding important environ- mental issues including climatic change and variability, biotic erosion and sustainable landuse, and will dramatically improve our estimation of global biomass and carbon stocks, fractional forest cover, forest extent and condition. It will also provide canopy data critical for biodiversity, natural hazard, and climate studies. Scheduled for launch in early 2000, VCL is an active lidar remote sensing system consisting of a five-beam instrument with 25 m contiguous along track resolution. The five beams are in a circular configuration 8 km across and each beam traces a separate ground track spaced 2 km apart, eventually producing 2 km coverage between 65° N and S. VCL’s core measurement objectives are: (1) canopy top heights; (2) vertical distribution of intercepted surfaces (e.g. leaves and branches); and, (3) ground surface topographic elevations. These measurements are used to derive a variety of science data products including canopy heights, canopy vertical distribution, and ground elevations gridded monthly at 1° resolution and every 6 months at 2 km resolution, as well as a 2 km fractional forest cover product.

VideoTrails: Representing and Visualizing Structure in Video Sequences - Kobla,V.; David Doermann; Faloutsos,C. (Proceedings of the ACMInternational Multimedia Conference, 1997)

The virtual microscope. - Ferreira,R.; Moon,B.; Humphries,J.; Sussman, Alan; Saltz, J.; Miller,R.; Demarzo,A. (Proceedings of the AMIA Annual Fall Symposium, 1997)

Visual surveillance of human activity - Davis, Larry S.; Fejes,S.; Harwood,D.; Yacoob,Yaser; Hariatoglu,I.; Black,M. (Computer Vision—ACCV'98, 1997)

A zooming web browser - Bederson, Benjamin B.; Hollan,J.D.; Stewart,J.; Rogers,D.; Druin, Allison; Vick,D.; Ring,L.; Grose,E.; Forsythe,C. (Human Factors in Web Development, 1997)

Applying algebraic and differential invariants for logo recognition - David Doermann; Rivlin,E.; Weiss, I. (Machine Vision and Applications, 1996)
The problem of logo recognition is of great interest in the document domain, especially for document databases. By recognizing the logo we obtain semantic information about the document which may be useful in deciding whether or not to analyze the textual components. Given a logo block candidate from a document image and alogo database, we would like to determine whether the region corresponds to a logo in the database. Similarly, if we are given a logo block candidate and adocumentdatabase, we wish to determine whether there are any documents in the database of similar origin. Both problems require indexing into a possibly large model space.In this contribution, we present a novel application of algebraic and differential invariants to the problem of logo recognition. By using invariants we have shape descriptors for matching that are unique and independent of the point of view. The algebraic invariants handle cases in which the whole shape of the logo is given and it is easy to describe. The differential invariants cover complex arbitrary logo shape and handle situations in which only part of the logo is recovered. We outline a hierarchical approach to logo recognition and define methods for page segmentation, feature extraction, and indexing. We demonstrate our approach and present results on a database of approximately 100 logos.

Archiving, indexing, and retrieval of video in compressed domain - Kobla,V.; David Doermann; Lin,K-I. (SPIEConference on Multimedia Storage and Archiving Systems, 1996)

Compressed Video Segmentation - Kobla,Vikrant; David Doermann; Rosenfeld,Azriel (University of Maryland, College Park, 1996)
Segmentation of video into shots and scenes in the compressed domain allows rapid, real-time analysis of video content using standard hardware. This paper presents robust techniques for parsing MPEG-compressed video sequences into shots based on their physical structure and further into scenes based on their semantic structure by identifying changes in content and camera motion. The analysis is performed in the compressed domain using available macroblock and motion vector information, and if necessary, DCT information. Motion vector analysis yields a qualitative description of the camera motion and is used to subdivide shots into subshots. Key frames for the shots and scenes can be used for browsing, indexing, and retrieval.

Compressed-domain document retrieval and analysis - Kia,Omid E; David Doermann; Chellapa, Rama (SPIE Conference of Multimedia Storage and Archiving Systems, 1996)
In this paper, we first describe a structural compression technique which has been designed to facilitate document text image storage, retrieval, and processing. This technique provides an efficient representation of textural images and lends itself to lossy compression, progressive transmission, direct access to sub-regions of the document and document processing in the compressed domain. We describe a data structure which can be used to efficiently store the compressed information, provide algorithms for creating and manipulating it, and present results of document processing on images compressed form the University of Washington database.

Computing 3-D head orientation from a monocular image sequence - Horprasert,T.; Yacoob,Yaser; Davis, Larry S. (Automatic Face and Gesture Recognition, 1996., Proceedings of the Second International Conference on, 1996)
An approach for estimating 3D head orientation in a monocular image sequence is proposed. The approach employs recently developed image-based parameterized tracking for face and face features to locate the area in which a sub-pixel parameterized shape estimation of the eye's boundary is performed. This involves tracking of five points (four at the eye corners and the fifth is the lip of the nose). The authors describe an approach that relies on the coarse structure of the face to compute orientation relative to the camera plane. Our approach employs projective invariance of the cross-ratios of the eye corners and anthropometric statistics to estimate the head yaw, roll and pitch. Analytical and experimental results are reported
Keywords: 3D head orientation computation; anthropometric statistics; camera plane; coarse structure; eye; eye boundary; eye corners; face features; face recognition; Feature extraction; head pitch; head roll; head yaw; Image sequences; image-based parameterized tracking; monocular image sequence; projective cross-ratio invariance; sub-pixel parameterized shape estimation; tracking

Designing Multimedia Environments for Children: Computers, Creativity, and Kids. - Druin, Allison; Solomon,C. (Wiley Computer Publishing, John Wiley and Sons, Inc., One Wiley Drive, Somerset, NJ 08875 ($44.95; Canada, $62.95); phone (Eastern Division): 201-469-4400;(Western Division): 801-972-5828., 1996)

The Development of a General Framework for Intelligent Document Image Retrieval - David Doermann; Sauvola,J.; Kauniskangas,H.; Shin,C.; Pietikainen,M.; Rosenfeld, A. (Proceedings in the International Workshop on Document Analysis Systems, 1996)

Differential expression of the expression site-associated gene I family in African trypanosomes - Morgan,R. W; El‐Sayed, Najib M.; Kepa,J. K; Pedram,M.; Donelson,J. E (Journal of Biological Chemistry, 1996)

Feature Normalization for Video Indexing and Retrieval - Kobla,Vikrant; David Doermann; Lin,King-Ip (David); Faloutsos,Christos (University of Maryland, College Park, 1996)
Fast and efficient storage, browsing, indexing, and retrieval of video is necessary for the development of various multimedia database applications. Given that video is typically stored efficiently in a compressed format, if we can analyze the compressed representation directly, we can avoid the costly overhead of decompressing and operating at the pixel level. Compressed domain parsing of video has been presented in earlier work where key frames are identified for shots, subshots, and scenes. In this paper, we describe key frame selection, feature extraction, indexing, and retrieval techniques that are directly applicable to MPEG-compressed video. We develop a frame-type independent representation of the various types of frames present in an MPEG video in which all frames can be considered equivalent. Features are derived from the available DCT, macroblock, and motion vector information and mapped to a low-dimensional space where they can be accessed using standard database techniques. The spatial information is used as primary index while the temporal information is used to enhance the robustness of the system during the retrieval process. The techniques presented enable fast archiving, indexing, and retrieval of video. Our operational prototype typically takes a fraction of a second to retrieve similar video scenes from our database, with over 95% success.

The Function of Documents - David Doermann; Rivlin,Ehud; Rosenfeld,Azriel (University of Maryland, College Park, 1996)
The purpose of a document is to facilitate the transfer of information from its author to its readers. It is the author's job to design the document so that the information it contains can be interpreted accurately and efficiently. To do this, the author can make use of a set of stylistic tools. In this paper we introduce the concept of document functionality, which attempts to describe the roles of documents and their components in the process of transferring information. A functional description of a document provides insight into the type of the document, into its intended uses, and into strategies for automatic document interpretation and retrieval. To demonstrate these ideas, we define a taxonomy of functional document components and show how functional descriptions can be used to reverse-engineer the intentions of the author, to navigate in document space, and to provide important contextual information to aid in interpretation.

Generating redesign suggestions to reduce setup cost: a step towards automated redesign - Das,Diganta; Gupta, Satyandra K.; Nau, Dana S. (Computer-Aided Design, 1996)
All mechanical designs pass through a series of formal and informal redesign steps, involving the analysis of functionality, manufacturability, cost and other life-cycle factors. The speed and efficacy of these steps has a major influence on the lead time of the product from conceptualization to launching. In this paper we propose a methodology for automatically generating redesign suggestions for reducing setup costs for machined parts.Given an interpretation of the design as a collection of machinable features, our approach is to generate alternate machining features by making geometric changes to the original features, and add them to the feature set of the original part to create an extended feature set. The designer may provide restrictions on the design indicating the type and extent of modifications allowed on certain faces and volumes, in which case all redesign suggestions generated by our approach honour those restrictions. By taking combinations of features from the extended feature set generated above, we can generate modified versions of the original design that still satisfy the designer's intent. By considering precedence constraints, we can estimate the setup time that will be required for each design. Any modified design whose setup time is less than that of the original design can be presented to the designer as a possible way to modify the original design.

A high performance image database system for remotely sensed imagery - Shock,C.; Chang,C.; Davis, Larry S.; Goward,S.; Saltz, J.; Sussman, Alan (Euro-Par'96 Parallel Processing, 1996)

Local tools: an alternative to tool palettes - Bederson, Benjamin B.; Hollan,J.D.; Druin, Allison; Stewart,J.; Rogers,D.; Proft,D. (Proceedings of the 9th annual ACM symposium on User interface software and technology, 1996)

A Multi-Level Approach to Interlingual MT: Defining the Interface between Representational Languages - Dorr, Bonnie J; Voss,C.R. (International Journal of Expert Systems, 1996)
This paper describes a multi-level design, i.e., a non-uniform approach to interlingual ma-chine translation (MT), in which distinct representational languages are used for di erent types of knowledge. We demonstrate that a linguistically-motivated \division of labor" across multiple representation levels has not complicated, but rather has readily facilitated, the identi cation and construction of systematic relations at the interface between each level. Our approach assumes an interlingua derived from the lexical semantics and predi- cate decomposition approaches of Jackendo (1983; 1990) and Levin and Rappaport-Hovav (1995a; 1995b). We describe a model of interpretation and representation of natural lan- guage sentences which has been implemented as part of an interlingual MT system called PRINCITRAN.

Multilingual generation: The role of telicity in lexical choice and syntactic realization - Dorr, Bonnie J; Olsen,Mari Broman (Machine Translation, 1996)
Multilingual generation in machine translation (MT) requires a knowledge organization that facilitates the task of lexical choice, i.e. selection of lexical units to be used in the generation of a target-language sentence. This paper investigates the extent to which lexicalization patterns involving the lexical aspect feature [+telic] may be used for translating events and states among languages. Telicity has been correlated syntactically with both transitivity and unaccusativity, and semantically with Talmy's ‘path’ of a motion event, the representation of which characterizes languages parametrically.

Parallel algorithms for image enhancement and segmentation by region growing, with an experimental study - Bader, D.A.; JaJa, Joseph F.; Harwood,D.; Davis, Larry S. (The Journal of Supercomputing, 1996)
This paper presents efficient and portable implementations of a powerful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique that makes use of the SNF and a variant of the conventional connected components algorithm which we call delta-Connected Components. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The image segmentation algorithm makes use of an efficient connected components algorithm based on a novel approach for parallel merging. The algorithms have been coded in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results are consistent with the theoretical analysis (and provide the best known execution times for segmentation, even when compared with machine-specific implementations). Our test data include difficult images from the Landsat Thematic Mapper (TM) satellite data.

Quantitative Measurement of the Performance of Raster-to-vector Conversion Algorithms - Hori,O.; David Doermann (Graphics Recognition: Methods and ApplicationsGraphics Recognition: Methods and Applications, 1996)

Query previews in networked information systems - Donn,K.; Plaisant, Catherine; Shneiderman, Ben (Research and Technology Advances in Digital Libraries, 1996. ADL '96., Proceedings of the Third Forum on, 1996)
In a networked information system (such as the NASA Earth Observing System-Data Information System (EOS-DIS)), there are three major obstacles facing users in a querying process: network performance, data volume and data complexity. In order to overcome these obstacles, we propose a two phase approach to query formulation. The two phases are the Query Preview and the Query Refinement. In the Query Preview phase, users formulate an initial query by selecting rough attribute values. The estimated number of matching data sets is shown, graphically on preview bars which allows users to rapidly focus on a manageable number of relevant data sets. Query previews also prevent wasted steps by eliminating zero hit queries. When the estimated number of data sets is long enough, the initial query is submitted to the network which returns the metadata of the data sets for further refinement in the Query Refinement phase. The two phase approach to query formulation overcomes slow network performance, and reduces the data volume and data complexity, problems. This approach is especially appropriate for users who do not have extensive knowledge about the data and who prefer an exploratory method to discover data patterns and exceptions. Using this approach, we have developed dynamic query user interfaces to allow users to formulate their queries across a networked environment
Keywords: attribute; complexity; data; data; Earth; environment; networked; EOS-DIS; NASA; formulation; querying; formulation; user; hit; information; interfaces; interfaces; exploratory; method; matching; networks; information; Observing; patterns; data; performance; networked; Preview; Query; process; rough; queries; computer; query; refinement; data; retrieval; information; services; interactive; sets; network; System-Data; System; Query; systems; query; user; values; zero; volume; dynamic

Query previews in networked information systems - Donn,K.; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the Third Forum on Research and Technology Advances in Digital Libraries, 1996. ADL '96, 1996)
In a networked information system (such as the NASA Earth Observing System-Data Information System (EOS-DIS)), there are three major obstacles facing users in a querying process: network performance, data volume and data complexity. In order to overcome these obstacles, we propose a two phase approach to query formulation. The two phases are the Query Preview and the Query Refinement. In the Query Preview phase, users formulate an initial query by selecting rough attribute values. The estimated number of matching data sets is shown, graphically on preview bars which allows users to rapidly focus on a manageable number of relevant data sets. Query previews also prevent wasted steps by eliminating zero hit queries. When the estimated number of data sets is long enough, the initial query is submitted to the network which returns the metadata of the data sets for further refinement in the Query Refinement phase. The two phase approach to query formulation overcomes slow network performance, and reduces the data volume and data complexity, problems. This approach is especially appropriate for users who do not have extensive knowledge about the data and who prefer an exploratory method to discover data patterns and exceptions. Using this approach, we have developed dynamic query user interfaces to allow users to formulate their queries across a networked environment
Keywords: Computer networks; data complexity; data mining; data patterns; data volume; dynamic query user interfaces; Educational institutions; EOS-DIS; exploratory method; Information retrieval; Information services; Information systems; Intelligent networks; interactive systems; Laboratories; Manipulator dynamics; matching data sets; NASA Earth Observing System-Data Information System; Network performance; networked environment; networked information systems; query formulation; query preview; query refinement; querying process; rough attribute values; User interfaces; visual databases; zero hit queries

Recognition of head gestures using hidden markov models - Morimoto,C.; Yacoob,Yaser; Davis, Larry S. (Pattern Recognition, 1996., Proceedings of the 13th International Conference on, 1996)

Recognizing human facial expressions from long image sequences using optical flow - Yacoob,Yaser; Davis, Larry S. (IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996)
An approach to the analysis and representation of facial dynamics for recognition of facial expressions from image sequences is presented. The algorithms utilize optical flow computation to identify the direction of rigid and nonrigid motions that are caused by human facial expressions. A mid-level symbolic representation motivated by psychological considerations is developed. Recognition of six facial expressions, as well as eye blinking, is demonstrated on a large set of image sequences
Keywords: Computer vision; Eyebrows; face recognition; facial dynamics; Facial features; human facial expression recognition; HUMANS; Image motion analysis; image recognition; image representation; Image sequences; Motion analysis; Motion estimation; Optical computing; optical flow; symbolic representation; tracking

Role of word sense disambiguation in lexical acquisition: predicting semantics from syntactic cues - Dorr, Bonnie J; Jones,Doug (Proceedings of the 16th conference on Computational linguistics - Volume 1, 1996)
This paper addresses the issue of word-sense ambiguity in extraction from machine-readable resources for the construction of large-scale knowledge sources. We describe two experiments: one which ignored word-sense distinctions, resulting in 6.3% accuracy for semantic classification of verbs based on (Levin, 1993); and one which exploited word-sense distinctions, resulting in 97.9% accuracy. These experiments were dual purpose: (1) to validate the central thesis of the work of (Levin, 1993), i.e., that verb semantics and syntactic behavior are predictably related; (2) to demonstrate that a 15-fold improvement can be achieved in deriving semantic information from syntactic cues if we first divide the syntactic cues into distinct groupings that correlate with different word senses. Finally, we show that we can provide effective acquisition techniques for novel word senses using a combination of online sources.

Structural compression for document analysis - Kia,O. E; David Doermann (Pattern Recognition, 1996., Proceedings of the 13th International Conference on, 1996)
In this paper we describe a structural compression technique to be used for document text image storage and retrieval. The primary objective is to provide an efficient representation, storage, transmission and display. A secondary objective is to provide an encoding which allows access to specified regions within the image and facilitates traditional document processing operations without requiring complete decoding. We describe an algorithm which symbolically decomposes a document image and structurally orders the error bitmap based on a probabilistic model. The resultant symbol and error representations lend themselves to reasonably high compression ratios and are structured so as to allow operations directly on the compressed image. The compression scheme is implemented and compared to traditional compression methods
Keywords: analysis; document; bitmap; error; coding; image; compression; compression; document; compression; symbol; decomposition; data; image; manipulation; processing; image; ratios; document; recognition; probability; symbol; representations; structural; representations; symbolic; retrieval; document; storage; error; text

Structure Preserving Document Image Compression and Transmission - Kia,O.; David Doermann (ICIP, 1996)

Table-Form Structure Analysis Based on Box-Driven Reasoning - Hori,Osamu; David Doermann (IEICE TRANSACTIONS on Information and Systems, 1996)
Table-form document structure analysis is an important problem in the document processing domain. This paper presents a new method called Box-Driven Reasoning (BDR) to robustly analyze the structure of table-form documents that include touching characters and broken lines. Real documents are copied repeatedly and overlaid with printed data, resulting in characters that touch cells and lines that are broken. Most previous methods employ a line-oriented approach, but touching characters and broken lines make the procedure fail at an early stage. BDR deals with regions directly in contrast with other previous methods and a reduced resolution image is introduced to supplement information deteriorated by noise. Experimental tests show that BDR reliably recognizes cells and strings in document images with touching characters and broken lines.

A Theory of Document Functionality - Rivlin,E.; Doermann, David; Rosenfeld, A. (Proceedings in FLAIRS, 1996)

Use of Syntactic and Semantic Filters for Lexical Acquisition: Using WordNet to Increase Precision - Dorr, Bonnie J; Jones,Doug (In Proceedings of the Workshop on Predicative Forms in Natural Language and Lexical Knowledge Bases, 1996)
This paper describes an approach to automatic extraction of verb meanings from machinereadable resources for the construction of large-scale knowledge sources. We describe semantic filters designed to reduce the number of incorrect assignments made by a purely syntactic technique. We report on our results of disambiguating the verbs in the semantic filters by adding WordNet sense annotations.

Artificial Intelligence: Theory and Practice - Dean, Thomas L.; ALLEN, JAMES AUTOR; Aloimonos, J. (Benjamin/Cummings Pub., 1995)
This book provides a detailed understanding of the broad issues in artificial intelligence and a useful survey of current AI technology. The author delivers broad coverage of innovative representational techniques, including neural networks, image processing, and probabilistic reasoning, alongside the traditional methods of symbolic reasoning. AI algorithms are described in detailed prose in the text and fully implemented in LISP at the ends of chapters. A stand-alone LISP chapter makes an excellent reference and refresher. Each chapter includes a detailed description of an AI application.
Keywords: Computers / Expert Systems; Computers / Intelligence (AI) & Semantics

Automated Manufacturability Analysis: A Survey - Das,Diganta; Gupta, Satyandra K.; Regli,W. C.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 1995)
In the marketplace of the 21st century, there is no place for traditional ``over-the-wall'' communications between design and manufacturing. In order to ``design it right the very first time,'' designers must ensure that their products are both functional and easy to manufacture. Software tools have had some successes in reducing the barriers between design and manufacturing. Manufacturability analysis systems are emerging as one such tool---enabling identification of potential manufacturing problems during the design phase and providing suggestions to designers on how to eliminate them. In this paper, we provide a survey of current state of the art in automated manufacturability analysis. We present the historical context in which this area has emerged and outline characteristics to compare and classify various systems. We describe the two dominant approaches to automated manufacturability analysis and overview representative systems based on their application domain. We describe support tools that enhance the effectiveness of manufacturability analysis systems. Finally, we attempt to expose some of the existing research challenges and future directions.
Keywords: manufacturability; Manufacturing; Solid modeling; Systems Integration Methodology

Building a LCS-Based Lexicon in TAGs - Dorr, Bonnie J; Palmer,M. (Proceedings of the AAAI-95 Spring Symposium Series, Representation and Acquisition of Lexical Knowledge: Polysemy, Ambiguity, and Generativity, Stanford, CA, March, 1995)

cDNA expressed sequence tags of Trypanosoma brucei rhodesiense provide new insights into the biology of the parasite - El‐Sayed, Najib M.; Alarcon,Clara M.; Beck,John C.; Sheffield,Val C.; Donelson,John E. (Molecular and Biochemical Parasitology, 1995)
A total of 518 expressed sequence tags (ESTs) have been generated from clones randomly selected from a cDNA library and a spliced leader sub-library of a Trypanosoma brucei rhodesiense bloodstream clone. 205 (39%) of the clones were identified based on matches to 113 unique genes in the public databases. Of these, 71 cDNAs display significant similarities to genes in unrelated organisms encoding metabolic enzymes, signal transduction proteins, transcription factors, ribosomal proteins, histones, a proliferation-associated protein and thimet oligopeptidase, among others. 313 of the cDNAs are not related to any other sequences in the databases. These cDNA ESTs provide new avenues of research for exploring both the novel trypanosome-specific genes and the genome organization of this parasite, as well as a resource for identifying trypanosome homologs to genes expressed in other organisms.
Keywords: cDNA; Expressed sequence tag; Trypanosoma brucei rhodesiense

Current Trends and Future Challenges in Automated Manufacturability Analysis - Gupta, Satyandra K.; Das,Diganta; Regli,W. C.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 1995)
In the marketplace of the 21st century, there is no place for traditional communications between design and manufacturing. In order to ``design it right the first time,'' designers must ensure that their products are both functional and easy to manufacture. Software tools have had some successes in reducing the barriers between design and manufacturing. Manufacturability analysis systems are emerging as one such tool---enabling identification of potential manufacturing problems during the design phase and providing suggestions to designers on how to eliminate them. In this paper, we survey of current state of the art in automated manufacturability analysis. We describe the two dominant approaches to automated manufacturability analysis and overview representative systems based on their application domain. Finally, we attempt to expose some of the existing research challenges and future directions.
Keywords: computer integrated manufacturing; manufacturability; Manufacturing; Solid modeling; Systems Integration Methodology

Development of interlingual lexical conceptual structures with syntactic markers for machine translation - Dorr, Bonnie J; Lee,J.; Voss,C.; Suh,S. (University of Maryland, 1995)
This document reports on research conducted at the University of Mary-land for the Korean/English Machine Translation (MT) project. Our pri- mary objective was to develop an interlingual representation based on lexical conceptual structure (LCS) and to examine the relation between this repre- sentation and a set of linguistically motivated semantic classes. We view the work of the past year as a critical step toward achieving our goal of building a generator: the classification of LCS's into a semantic hierarchy provides a systematic mapping between semantic knowledge about verbs and their surface syntactic structures. We have focused on several areas in support of our objectives: (1) inves- tigation of morphological structure including distinctions between Korean and English; (2) porting a fast, message-passing parser to Korean (and to the IBM PC); (3) study of free word order and development of the associ- ated processing algorithm; (4) investigation of the aspectual dimension as it impacts morphology, syntax, and lexical semantics; (5) investigation of the relation between semantic classes and syntactic structure; (6) develop- ment of theta-role and lexical-semantic templates through lexical acquisition techniques; (7) definition a mapping between KR concepts and interlingual representations; (8) formalization of the lexical conceptual structure

Efficient parsing for Korean and English: A parameterized message-passing approach - Dorr, Bonnie J; Lee,J.; Lin,D.; Suh,S. (Computational Linguistics, 1995)

Estimation of setup time for machined parts: accounting for work-holding constraints using a vise - Das,D.; Gupta,S.K.; Nau, Dana S. (COMPUTERS IN ENGINEERING, 1995)
For machined parts, setup time is a major component ofthe total time required to manufacture a machined part from a stock. If the number of setups and hence setup time can be reduced, this will not only decrease the manufacturing time, but will also ensure better machining accuracy, require fewer work-holding devices and increase machine usage time. To achieve any improvement in setup time, rst we need to estimate the setup time accurately. In this paper we pro- pose a methodology to estimate the setup time for machin- ing prismatic parts in a three axis vertical machining center. We concurrently consider three major factors for estimating the number of setups, namely|the precedence constraints among machining operations, the feasibility of work holding using vise clamping, and the availability of datum faces for locating the workpiece on the machine table during machin- ing on a 3 axis vertical machining center.

Euclidean spanners: short, thin, and lanky - Arya,Sunil; Das,Gautam; Mount, Dave; Salowe,Jeffrey S.; Smid,Michiel (Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995)

Evaluation and selection of biases in machine learning - Gordon,Diana F.; desJardins, Marie (Machine Learning, 1995)
In this introduction, we define the term bias as it is used in machine learning systems. We motivate the importance of automated methods for evaluating and selecting biases using a framework of bias selection as search in bias and meta-bias spaces. Recent research in the field of machine learning bias is summarized.

Experimental investigation of high performance cognitive and interactive text filtering - Oard, Douglas; DeClaris,N.; Dorr, Bonnie J; Faloutsos,C.; Marchionini,G. (, IEEE International Conference on Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century, 1995)
Text filtering has become increasingly important as the volume of networked information has exploded in recent years. This paper reviews recent progress in that field and reports on the development of a testbed for experimental investigation of cognitive and interactive text selection based on a history of user evaluations. An interactive filtering system model is presented and a new cognitive filtering technique which the authors call the Gaussian User Model is described. Because development of analytic measures of text selection effectiveness has proven intractable, the authors have modified the Cornell SMART text retrieval system to create a flexible text filtering testbed for experimental determination of filtering effectiveness. The paper concludes with a description of the design of this testbed system
Keywords: Cause effect analysis; Computer science; Contracts; Cornell SMART text retrieval system; Educational institutions; Gaussian User Model; high performance cognitive interactive text filtering; History; Information filtering; Information filters; Information retrieval; information retrieval system evaluation; Libraries; Matched filters; online front-ends; Query processing; System testing; text selection effectiveness; user evaluations; User interfaces; user modelling

Generating Synthetic Data for Text Analysis Systems - David Doermann; Yao,S. (SDAIR, 1995)
In this paper we describe work on a sys-tem for modeling errors in the output of OCR systems. The project is motivated by the desire to evaluate the performance of various text analysis systems under varying, yet controlled conditions. We describe a set of symbol and page models which are used to degrade an ideal text by introducing er- rors which typically occur during scanning, decomposition and recognition of document images. A rst generation of the software is described which implements the page mod- els and allows the use of transition proba- bilities, either extracted from real data or generated synthetically, to corrupt text.

How to succeed in graduate school: A guide for students and advisors - desJardins, Marie (International Amateur-Professional Photoelectric Photometry Communications, 1995)

How to succeed in graduate school: a guide for students and advisors: part II of II - desJardins, Marie (Crossroads, 1995)

Hybrid thinning through reconstruction - David Doermann; Kia,O. (Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, 1995)
One difficulty with many pixel-wise thinning algorithms is that they produce unacceptable results at junction points, or in the presence of contour noise. The authors present a novel approach to detecting ambiguous regions in a thinned image. The method uses the reconstructability properties of appropriate thinning algorithms to reverse the thinning process and automatically detect those pixels which may have resulted from more then one stroke in the image. The ambiguous regions are then interpreted and reconstructed using domain specific or derived contextual information. The approach has the advantage of using local methods to rapidly identify strokes (or regions) which have been thinned correctly and allowing more detailed analysis based on non-local methods in the remaining regions
Keywords: algorithms; edge; ambiguous; detection; automatic; detection; contextual; detection; image; information; contour; methods; nonlocal; methods; pixel-wise; noise; hybrid; Pixel; points; local; reconstruction; image; region; segmentation; noise; stroke; junction; thinning; thinning; image

Image Analysis and Processing: 8th International Conference, Iciap '95, San Remo, Italy, September 13-15, 1995 : Proceedings - Braccini,Carlo; De Floriani, Leila; Vernazza,Gianni (Springer, 1995)
This book presents the proceedings of the 8th International Conference on Image Analysis and Processing, ICIAP '95, held in Sanremo, Italy in September 1995 under the sponsorship of the International Association of Pattern Recognition IAPR.The volume presents 108 papers selected from more than 180 submissions together with six invited contributions. The papers are written by a total of 265 contributing authors and give a comprehensive state-of-the-art report on all current issues of image analysis and processing. Theoretical aspects are addressed as well as systems design and advanced applications, particularly in medical imaging.
Keywords: Artificial intelligence; COMPUTER AIDED DESIGN; Computer Graphics; Computer science; Computer vision; Computers / CAD-CAM; Computers / Computer Graphics; Computers / Computer Science; Computers / Computer Vision & Pattern Recognition; Computers / Image Processing; Computers / Intelligence (AI) & Semantics; Computers / Optical Data Processing; Computers / Software Development & Engineering / General; Electronic books; IMAGE PROCESSING; Image processing/ Congresses; Imaging systems; Optical data processing; Optical pattern recognition; software engineering

Land cover dynamics investigation using parallel computers - Liang, S.; Davis, Larry S.; Townshend,J.; Chellapa, Rama; DeFries, R.; Dubayah, R.; Goward,S.; JaJa, Joseph F.; Krishnamachar, S.; Roussopoulos, Nick; Saltz, J.; Samet, Hanan; et al. (Geoscience and Remote Sensing Symposium, 1995. IGARSS '95. 'Quantitative Remote Sensing for Science and Applications', International, 1995)
A comprehensive and highly interdisciplinary research program is being carried out to investigate global land cover dynamics in heterogeneous parallel computing environments. Some of the problems are addressed including atmospheric correction, mixture modeling, image classifications by Markovian random fields and by segmentation, global image/map databases, object oriented parallel programming and parallel/IO. During the initial two years project, significant progress has been made in all of these areas
Keywords: geographic information system; geophysical measurement technique; geophysics computing; image classification; image map database; image segmentation; land cover dynamics; land surface; mixture modeling; object oriented programming; optical imaging; para; GIS; IR imaging; Markovian random fields; atmospheric correction

Lexical allocation in interlingua-based machine translation of spatial expressions - Voss,C.R.; Dorr, Bonnie J; Sencan,M.U. (Working Notes for IJCAI-95 Workshop on the Representation and Processing of Spatial Expressions, Montreal, Canada, 1995)
Given a spatial expression, or its computationalsemantic form, how is the expression’s spatial semantics to be allocated lexically, i.e., among entries in the lexicon? In interlingua-based ma- chine translation (MT) research, lexical alloca- tion is the problem of allocating or subdividing a linguistic expression’s full interlingual (IL) structure into the substructures that are lexical IL forms, i.e., in the lexicon. Here we present our work developing IL forms and an IL lexicon for translating English spatial expressions into Turkish. We examine several co-occurrence patterns between motion verbs (spatial place- ment and displacement) and directional adpo- sitions (particles in English, postpositions in Turkish) and the lexical allocation of spatial vectors in these patterns

M.H.M: Euclidean spanners: short, thin, and lanky - Arya,Sunil; Dast,Gautam; Mount, Dave; Salowe,Jeffrey S.; Smid,Michiel (In: 27th ACM Symposium on Theory of Computing, 1995)
Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest path length between each pair of points is not more than a constant factor longer than the Euclidean distance between the points. In many applications of spanners, it is important that the spanner possess a number of additional properties: low tot al edge weight, bounded degree, and low diameter. Existing research on spanners has considered one property or the other. We show that it is possible to build spanners in optimal O (n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these *Max-Planck-Institut fiir Informatik, D-66123 Saarbrucken,

QUERY PREVIEWS IN NETWORKED INFORMATION SYSTEMS - Doan,K.; Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 1995)
In a networked information system, there are three major obstacles facing users in a querying process: network performance, data volume and data complexity. In order to overcome these obstacles, we propose a two-phase approach to dynamic query formulation by volume preview. The two phases are the Query Preview and Query Refinement. In the Query Preview phase, users formulate an initial query by selecting desired attribute values. The volume of matching data sets is shown graphically on preview bars which aid users to rapidly eliminate undesired data sets, and focus on a manageable number of relevant data sets. Query previews also prevent wasted steps by eliminating zero-hit queries. When the estimated number of data sets is low enough, the initial query is submitted to the network, which returns the metadata of the data sets for further refinement in the Query Refinement phase. The two-phase approach to query formulation overcomes slow network performance, and reduces the data volume and data complexity problems. This approach is especially appropriate for users who prefer the exploratory method to discover data patterns and exceptions during the query formulation process. Using this approach, we have developed dynamic query user interfaces to allow users to formulate their queries across a networked environment.

The representation of document structure: A generic object-process approach - Dori,D.; David Doermann; Shin,C.; Haralick,R.; Phillips,I.; Buchman,M.; Ross,D. (University of Maryland, College Park, 1995)

Representing a student’s learning states and transitions - Gurer,D.; desJardins, Marie; Schlager,M. (American Association of Artificial Intelligence Spring Symposium on Representing Mental States and Mechanisms, 1995)
We describe an ongoing project to develop an adaptive training system (ATS) that dynamically models a student’s learning processes and can provide specialized tutoring adapted to a student’s knowledge state and learning style. The student modeling component of the ATS, ML-Modeler, uses machine learning (ML) techniques to emulate the student’s novice-toexpert transition. ML-Modeler infers which learning methods the student has used to reach the current knowledge state by comparing the student’s solution trace to an expert solution and generating plausible hypotheses about what misconceptions and errors the student has made. A case-based approach is used to generate hypotheses through incorrectly applying analogy, overgeneralization, and overspecialization. The student and expert models use a network-based representation that includes abstract concepts and relationships as well as strategies for problem solving. Fuzzy methods are used to represent the uncertainty in the student model. This paper describes the design of the ATS and ML-Modeler, and gives a detailed example of how the system would model and tutor the student in a typical session. The domain we use for this example is high-school level chemistry.

Robust table-form structure analysis based on box-driven reasoning - Hori,O.; David Doermann (Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, 1995)
Table form document structure analysis is an important problem in the document processing domain. The paper presents a method called Box Driven Reasoning (BDR) to robustly analyze the structure of table form documents which include touching characters and broken lines. Most previous methods employ a line oriented approach. Real documents are copied repeatedly and overlaid with printed data, resulting in characters which touch cells and lines which are broken. BDR deals with regions directly, in contrast with other previous methods. Experimental tests show that BDR reliably recognizes cells and strings in document images with touching characters and broken lines
Keywords: analysis; table; analysis; touching; BDR; box; characters; character; document; domain; robust; driven; form; image; images; document; lines; document; mechanisms; PROCESSING; processing; inference; reasoning; broken; recognition; data; structure; structures; document; table

Selecting Tense, Aspect, and Connecting Words In Language Generation - Dorr, Bonnie J; Gaasterland,Terry (In Proceedings of IJCAI-95, 1995)
Generating language that reflects the temporal organization of represented knowledge requires a language generation model that integrates contemporary theories of tense and aspect, temporal representations, and methods to plan text. This paper presents a model that produces complex sentences that reflect temporal relations present in underlying temporal concepts. The main result of this work is the successful application of constrained linguistic theories of tense and aspect to a generator which produces meaningful event combinations and selects appropriate connecting words that relate them. 1 Introduction Reasoning about temporal knowledge and formulating answers to questions that involve time necessitate the presentation of temporal information to users. One approach is to incorporate the temporal information directly into natural language paraphrases of the represented knowledge. This requires a method to plan language that contains not only tense selections, but aspect selections...

The SVD in Image Restoration - O'Leary, Dianne P. (SVD and Signal Processing III: Algorithms, Architectures, and ApplicationsSVD and Signal Processing III: Algorithms, Architectures, and Applications, 1995)

Toward a lexicalized grammar for interlinguas - Voss,Clare; Dorr, Bonnie J (Machine Translation, 1995)
In this paper we present one aspect of our research on machine translation (MT): capturing the grammatical and computational relation between (i) the interlingua (IL) as defined declaratively in the lexicon and (ii) the IL as defined procedurally by way of algorithms that compose and decompose pivot IL forms. We begin by examining the interlinguas in the lexicons of a variety of current IL-based approaches to MT. This brief survey makes it clear that no consensus exists among MT researchers on the level of representation for defining the IL. In the section that follows, we explore the consequences of this missing formal framework for MT system builders who develop their own lexical-IL entries. The lack of software tools to support rapid IL respecification and testing greatly hampers their ability to modify representations to handle new data and new domains. Our view is that IL-based MT research needs both (a) the formal framework to specify possible IL grammars and (b) the software support tools to implement and test these grammars. With respect to (a), we propose adopting a lexicalized grammar approach, tapping research results from the study of tree grammars for natural language syntax. With respect to (b), we sketch the design and functional specifications for parts of ILustrate, the set of software tools that we need to implement and test the various IL formalisms that meet the requirements of a lexicalized grammar. In this way, we begin to address a basic issue in MT research, how to define and test an interlingua as a computational language — without building a full MT system for each possible IL formalism that might be proposed.

AAAI 1994 Spring Symposium Series Reports - Woods,William; Uckun,Sendar; Kohane,Isaac; Bates,Joseph; Hulthage,Ingemar; Gasser,Les; Hanks,Steve; Gini,Maria; Ram,Ashwin; desJardins, Marie; Johnson,Peter; Etzioni,Oren; et al. (AI Magazine, 1994)

Adaptation of noncompetitive and competitive neural networks to focal lesions - Weinrich,M.; Sutton,G. G; Reggia, James A.; D'Autrechy,C. L (Journal of Artificial Neural Networks, 1994)

On automatic filtering of multilingual texts - Oard, Douglas; DeClaris,N.; Dorr, Bonnie J; Faloutsos,C. (, 1994 IEEE International Conference on Systems, Man, and Cybernetics, 1994. 'Humans, Information and Technology', 1994)
An emerging requirement to sift through the increasing flood of text information has led to the rapid development of information filtering technology in the past five years. This study introduces novel approaches for filtering texts regardless of their source language. We begin with a brief description of related developments in text filtering and multilingual information retrieval. We then present three alternative approaches to selecting texts from a multilingual information stream which represent a logical evolution from existing techniques in related disciplines. Finally, a practical automated performance evaluation technique is proposed
Keywords: automated performance evaluation; Business communication; Computer science; Discussion forums; Displays; Educational institutions; Floods; Government; Information filtering; Information filters; Information retrieval; multilingual information retrieval; multilingual text filtering; natural languages; performance evaluation

The Case for a MT Developers’ Tool with a Two-Component View of the Interlingua - Dorr, Bonnie J; Voss,C. (Proceedings of the First Conference of the Association for Machine Translation in the Americas, 1994)

Concept-based lexical selection - Dorr, Bonnie J; Voss,C.; Peterson,E.; Kiker,M. (Proceedings of the AAAI-94 Fall Symposium on Knowledge Representation for Natural Language Processing in Implemented Systems, 1994)

Cortical map reorganization as a competitive process - Sutton III,G. G.; Reggia, James A.; Armentrout,S. L; D'Autrechy,C. L (Neural Computation, 1994)

Document page decomposition by integration of distributed soft decisions - Etemad,K.; David Doermann; Chellapa, Rama (International Conference on Neural Networks, 1994)

Document Understanding at Maryland - David Doermann (IUW, 1994)

Estimating the heading direction using normal flow - Aloimonos, J.; Duric, Z. (International Journal of Computer Vision, 1994)

Evaluation of learning biases using probabilistic domain knowledge - desJardins, Marie (Proceedings of the workshop on Computational learning theory and natural learning systems (vol. 2) : intersections between theory and experiment: intersections between theory and experiment, 1994)

From syntactic encodings to thematic roles: Building lexical entries for interlingual MT - Dorr, Bonnie J; Garman,Joseph; Weinberg, Amy (Machine Translation, 1994)
Our goal is to construct large-scale lexicons for interlingual MT of English, Arabic, Korean, and Spanish. We describe techniques that predict salient linguistic features of a non-English word using the features of its English gloss (i.e., translation) in a bilingual dictionary. While not exact, owing to inexact glosses and language-to-language variations, these techniques can augment an existing dictionary with reasonable accuracy, thus saving significant time. We have conducted two experiments that demonstrate the value of these techniques. The first tested the feasibility of building a database of thematic grids for over 6500 Arabic verbs based on a mapping between English glosses and the syntactic codes in Longman's Dictionary of Contemporary English (LDOCE) (Procter, 1978). We show that it is more efficient and less error-prone to hand-verify the automatically constructed grids than it would be to build the thematic grids by hand from scratch. The second experiment tested the automatic classification of verbs into a richer semantic typology based on (Levin, 1993), from which we can derive a more refined set of thematic grids. In this second experiment, we show that a brute-force, non-robust technique provides 72% accuracy for semantic classification of LDOCE verbs; we then show that it is possible to approach this yield with a more robust technique based on fine-tuned statistical correlations. We further suggest the possibility of raising this yield by taking into account linguistic factors such as polysemy and positive and negative constraints on the syntax-semantics relation. We conclude that, while human intervention will always be necessary for the construction of a semantic classification from LDOCE, such intervention is significantly minimized as more knowledge about the syntax-semantics relation is introduced.
Keywords: humanities; Social Sciences and Law

Fully abstract characterizations of testing preorders for probabilistic processes - Yuen,S.; Cleaveland, Rance; Dayar,Z.; Smolka,S. (CONCUR'94: Concurrency Theory, 1994)

High performance computing for land cover dynamics - Parulekar,R.; Davis, Larry S.; Chellapa, Rama; Saltz, J.; Sussman, Alan; Townshend,J. (Pattern Recognition, 1994. Vol. 3-Conference C: Signal Processing, Proceedings of the 12th IAPR International Conference on, 1994)

How to succeed in graduate school: a guide for students and advisors: part I of II - desJardins, Marie (Crossroads, 1994)
This paper attempts to raise some issues that are important for graduate students to be successful and to get as much out of the process as possible, and for advisors who wish to help their students be successful. The intent is not to provide prescriptive advice -- no formulas for finishing a thesis or twelve-step programs for becoming a better advisor are given -- but to raise awareness on both sides of the advisor-student relationship as to what the expectations are and should be for this relationship, what a graduate student should expect to accomplish, common problems, and where to go if the advisor is not forthcoming.

ILustrate: a MT Developers’ Tool with a Two-Component View of the Interlingua - Dorr, Bonnie J; Voss,Clare R. (in Proceedings of the First AMTA Conference. Columbia MD, 1994)
The interlingua (IL) in machine translation (MT) systems can be defined in terms of two components: (i) "lexical IL forms " within language-specific lexicons where each lexical entry has associated with it one or more lexical representations, and (ii) algorithms for creating and decomposing the instantiated "pivot " representation. Within this framework, we examine five different approaches to the level of representation for the lexical IL forms and then discuss a tool, ILustrate, 2 we are building to develop and evaluate different IL representations coupled with their corresponding translation algorithms. 1

Instrument Grasp: AModel and its Effects on Handwritten Strokes - David Doermann; Varma,V.; Rosenfeld, A. (Pattern Recognition, 1994)

Introduction: Special issue on building lexicons for machine translation - Dorr, Bonnie J; Klavans,Judith (Machine Translation, 1994)

Jovian: A framework for optimizing parallel I/O - Bennett, R.; Bryant,K.; Sussman, Alan; Das,R.; Saltz, J. (Scalable Parallel Libraries Conference, 1994., Proceedings of the 1994, 1994)

Knowledge acquisition techniques for a military planning system - desJardins, Marie (Tools with Artificial Intelligence, 1994. Proceedings., Sixth International Conference on, 1994)
In order to build realistic AI planning systems, it is necessary to develop sophisticated tools for knowledge acquisition. This paper describes two knowledge acquisition tools for a crisis action planning system. The first is a graphical operator editor that enables users to develop new planning operators and revise existing operators. The second is an inductive learning system, based on the PAGODA learning model, that learns from simulator feedback and from choices made by the user during planning. This paper describes the work done so far, and proposed for the future, on these tools

Labeling of Human Face Components from Range Data - Yacoob,Yaser; Davis, Larry S. (CVGIP: Image Understanding, 1994)
An approach to labeling the components of human faces from range images is proposed. The components of interest are those humans usually find significant for recognition. To cope with the nonrigidity of faces, an entirely qualitative approach is used. The preprocessing stage employs a multistage diffusion process to identify convexity and concavity points. These points are grouped into components and qualitative reasoning about possible interpretations of the components is performed. Consistency of hypothesized interpretations is carried out using context-based reasoning. Experimental results on real range images of several faces are provided.

Machine translation divergences: a formal description and proposed solution - Dorr, Bonnie J (Comput. Linguist., 1994)
There are many cases in which the natural translation of one language into another results in a very different form than that of the original. The existence of translation divergences (i.e., crosslinguistic distinctions) makes the straightforward transfer from source structures into target structures impractical. Many existing translation systems have mechanisms for handling divergent structures but do not provide a general procedure that takes advantage of takes advantage of the systematic relation between lexical-semantic structure and syntactic structure. This paper demonstrates that a systematic solution to the divergence problem can be derived from the formalization of two types of information: (1) the linguistically grounded classes upon which lexical-semantic divergences are based; and (2) the techniques by which lexical-semantic divergences are resolved. This formalization is advantageous in that it facilitates the design and implementation of the system, allows one to make an evaluation of the status of the system, and provides a basis for proving certain important properties about the system.

Page Segmentation Using Decision Integration and Wavelet Packet Basis - Etemad,K.; David Doermann; Chellapa, Rama (ICPR, 1994)

A paradigm for non-head-driven parsing: Parameterized message-passing - Dorr, Bonnie J; Lin,D.; Lee,J.; Suh,S. (Proceedings of the International Conference on New Methods in Language Processing, Manchester, UK, 1994)

Planning-based integrated decision support systems - Bienkowski,M.A.; desJardins, Marie (Artificial Intelligence Planning Systems: Proceedings of the Second International Conference (AIPS-94), 1994)

Query transformation techniques for interoperable query processing in cooperative information systems - Raschid, Louiqa; Chang,Y.; Dorr, Bonnie J (Proceedings of the Second International Conference on Cooperative Information Systems (CoopIS94), May, 1994)

QUEST—Query Environment for Science Teaching - Shneiderman, Ben; Rosenfeld, A.; Marchioni,G.; Holliday,W.; Ricart, G.; Faloutsos,С.; Dick,J. (Digital Libraries' 94, 1994)
QUery Environment for Science Teaching (QUEST) is a proposed digital library implementation consisting of a set of research projects dealing with data capture and organization, content analysis, information seeking and visual interfaces.The QUEST team includes a large number of renown technical collaborators and prominent source collaborators, as well as a significant number of contributors in the University of Maryland, the central, co-ordinating agency.A large collection of multidisciplinary materials in visual and textual formats, made accessible to us by our source collaborators, will be organized to allow integrated access by users from the science education community, that is elementary school through college level teachers. QUEST will be structured so as to provide seamless access to widespread resources on disparate subjects. We intend to provide first-rate subject analysis and representation in order to provide ready access. QUEST will be accessible nationally by means of Mosaic. We propose to provide highly sophisticated querying, browsing and information investigation facilities which will handle integrated textual and visual materials without difficulty. They will be augmented by online reference and referral services, immediately accessible by the user. QUEST will provide a comprehensive information resource for science education accessible through a dynamic, visual user interface.

Recovery of Temporal Information from Static Images of Handwriting - David Doermann; Rosenfeld, A. (International Journal of Computer Vision, 1994)
The problem of off-line handwritten character recognition has eluded a satisfactory solution for several decades. Researchers working in the area of on-line recognition have had greater success, but the possibility of extracting on-line information from static images has not been fully explored. The experience of forensic document examiners assures us that in many cases, such information can be successfully recovered.We outline the design of a system for the recovery of temporal information from static handwritten images. We provide a taxonomy of local, regional and global temporal clues which are often found in hand-written samples, and describe methods for recovering these clues from the image. We show how this system can benefit from obtaining a comprehensive understanding of the handwriting signal and a detailed analysis of stroke and sub-stroke properties. We suggest that the recovery task requires that we break away from traditional thresholding and thinning techniques, and we provide a framework for such analysis. We demonstrate how isolated temporal clues can reliably be extracted from this framework and propose a control structure for integrating the partial information. We show how many seemingly ambiguous situations can be resolved by the derived clues and our knowledge of the writing process, and provide several examples to illustrate our approach. The support of this research by the Ricoh Corporation is gratefully acknowledged.

A simulation-based study on the concurrent execution of rules in a database environment - Raschid, Louiqa; Sellis,T.; Delis,A. (Journal of Parallel and Distributed computing, 1994)

Transforming queries from a relational schema to an object schema: A prototype based on F-logic - Chang,Yahui; Raschid, Louiqa; Dorr, Bonnie J (Methodologies for Intelligent SystemsMethodologies for Intelligent Systems, 1994)

Applying the CHAOS/PARTI library to irregular problems in computational chemistry and computational aerodynamics - Das,R.; Hwang,Y. S; Uysal, M.; Saltz, J.; Sussman, Alan (Scalable Parallel Libraries Conference, 1993., Proceedings of the, 1993)

Constraints on the Space of MT Divergences - Dorr, Bonnie J; Voss,C.R. (AAAI (1993), 1993)

Data parallel algorithms for the numerical modeling of semiconductor devices - Darling,James Paul (University of Maryland at College Park, 1993)

Document Image Understanding: Integrating Recovery and Interpretation - David Doermann (University of Maryland, College Park, 1993)

Early vision processing using a multi-stage diffusion process - Yacoob,Yaser; Davis, Larry S. (1993 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1993. Proceedings CVPR '93, 1993)
The use of a multistage diffusion process in the early processing of range data is examined. The input range data are interpreted as occupying a volume in 3-D space. Each diffusion stage simulates the process of diffusing part of the boundary of the volume into the volume. The outcome of the process can be used for both discontinuity detection and segmentation into shape homogeneous regions. The process is applied to synthetic noise-free and noisy step, roof, and valley edges as well as to real range images
Keywords: 3-D space; Computational modeling; Computer vision; Diffusion processes; discontinuity detection; early vision processing; Educational institutions; Image edge detection; Image segmentation; Laboratories; multistage diffusion process; Noise shaping; noise-free edges; noisy edges; Performance analysis; roof edges; segmentation; SHAPE; shape homogeneous regions; step edges; valley edges

A first-pass approach for evaluating machine translation systems - Jordan,P.W.; Dorr, Bonnie J; Benoit,J.W. (Machine Translation, 1993)
This paper describes a short-term survey and evaluation project that covered a large number of machine translation products and research. We discuss our evaluation approach and address certain issues and implications relevant to our findings. We represented a variety of potential users of MT systems and were faced with the task of identifying which systems would best help them solve their translation problems.

Image based typographic analysis of documents - David Doermann; Furuta,R. (Document Analysis and Recognition, 1993., Proceedings of the Second International Conference on, 1993)
An approach to image based typographic analysis of documents is provided. The problem requires a spatial understanding of the document layout as well as knowledge of the proper syntax. The system performs a page synthesis from the stream of formatting commands defined in a DVI file. Since the two-dimensional relationships between document components are not explicit in the page language, the authors develop a representation which preserves the two-dimensional layout, the read-order and the attributes of document components. From this hierarchical representation of the page layout we extract and analyze relevant typographic features such as margins, line and character spacing, and figure placement
Keywords: 2D; analysis; attributes; based; character; commands; component; data; description; document; DVI; extraction; feature; figure; file; formatting; hierarchical; image; language; languages; layout; line; margins; page; placement; processing; read-order; relationships; representation; spacing; spatial; structures; syntax; synthesis; typographic; understanding

Information mediation techniques for problem solving with multiple knowledge servers - Dorr, Bonnie J; Raschid, Louiqa (University of Maryland, 1993)
This paper describes two important information mediation prob-lems that arise when multiple knowledge and data servers are accessed for problem solving. The rst problem is building an intelligent interface be- tween a knowledge server (KS) and a processor (KP) so that queries may be answered intelligently and completely. The second problem is to provide interoperability among multiple KP/KS pairs so that a query may be an- swered using information from multiple sources. We present example scenar- ios which highlight each of these problems and then outline techniques and tasks that are applied towards obtaining a solution. These techniques draw upon disciplines such as query and transaction processing with knowledge bases and machine understanding and translation of natural language. The techniques for solving the information mediation problems described involve parameterized canonical representations (CR) for the KP/KS pairs. The CR will represent possible mappings between a query and the knowledge model and will be used during query transformation to produce a query which will provide more complete and correct answers. Parameterization will help in merging CRs to support interoperability for distributed problem solving.

Interlingual machine translation A parameterized approach - Dorr, Bonnie J (Artificial Intelligence, 1993)
The task of designing a machine translation system is difficult because, in order to achieve any degree of accuracy, such systems must capture language-independent information while still systematically processing many types of language-specific phenomena in each of the individual languages. This paper provides a catalog of certain types of distinctions among Spanish, English, and German, and describes a parameterized interlingual approach that characterizes these distinctions, both at the syntactic level and at the lexical-semantic level. The parameter-setting approach to machine translation is desirable because it simplifies the descriptions of natural grammars, facilitates the task of modifying and augmenting the system, accounts for cross-linguistic variation uniformly, and provides a more constrained theory of processing. The approach described here is implemented in a system called UNITRAN, an interlingual machine translation system that translates English, Spanish, and German bidirectionally.

Interoperable query processing with multiple heterogeneous knowledge servers - Raschid, Louiqa; Chang,Yahui; Dorr, Bonnie J (Proceedings of the second international conference on Information and knowledge management, 1993)

The Interpretation and Recognition of Interfering Strokes - David Doermann; Rosenfeld, A. (IWFHR, 1993)

Logo Recognition - David Doermann; Rivlin,E.; Weiss, I. (University of Maryland, College Park, 1993)

Logo Recognition using Geomentric Invariants - David Doermann; Rivlin,E.; Weiss, I. (ICDAR, 1993)

Machine Translation of Spatial Expressions: Defining the Relation betweenan Interlingua and a Knowledge Representation System - Dorr, Bonnie J; Voss,Clare R. (IN PROCEEDINGS OF TWELFTH CONFERENCE OF THE AMERICAN ASSOCIATION FOR ARTIFICIAL IN℡LIGENCE, 1993)
In this paper we present one aspect of our presents a clear case of where general as well as specific research on machine translation (MT): defining the re- real world knowledge should assist in eliminating inap- lation between the interlingua (IL) and a knowledge representation (KR) within an MT system. Our interest lies in the translation of natural language (NL) sentences where the "message" contains a spatial relation in particular, where the sentence conveys information about the location or path of physical entities in the real, physical world. We explore several arguments for clarifying the source of constraints on the particular IL structures needed to translate these sentences.

MANDATE: managing networks using database technology - Haritsa,J. R; Ball,M. O; Roussopoulos, Nick; Datta,A.; Baras,J. S (IEEE Journal on Selected Areas in Communications, 1993)
There has been a growing demand for the development of tools to manage enterprise communication networks. A management information database is the heart of a network management system-it provides the interface between all functions of the network management system and, therefore, has to provide sophisticated functionality allied with high performance. The authors introduce the design of MANDATE (MAnaging Networks using DAtabase TEchnology), a proposed database system for effectively supporting the management of large enterprise networks. The MANDATE design makes a conscious attempt to take advantage of the special characteristics of network data and transactions, and of advances in database technology, to efficiently derive some of the required management functionality
Keywords: Communication networks; database management systems; enterprise communication networks; Heart; Information management; interface; internetworking; Local area networks; management functionality; management information database; managing networks using database technology; MANDATE; Manufacturing; network operating systems; open systems; Optical fiber cables; Research and development management; Technology management; telecommunication network management; Transaction databases; wide area networks

On The Maximum Number of Intersections of Two Polyhedra in 2 and 3 Dimensions - Dillencourt,M. B; Mount, Dave; Saalfeld,A.J. (Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, Ontario, 1993)
We obtain exact bounds on the maximum number of in-tersections between two polygons with prescribed edge counts. In three dimensions, we obtain exact bounds on the number of intersecting face-pairs of two polyhe- dra with prescribed face counts when the polyhedra are convex, and lower bounds in the general case.

A new point of view on the mathematical structure of Maxwell's equations - Mayergoyz, Issak D; D'Angelo,J. (Magnetics, IEEE Transactions on, 1993)
It is emphasized that the Maxwell equations have a peculiar mathematical structure which leads to boundary value problems with an overspecified number of partial differential equations and an underspecified number of boundary conditions. An attempt is made to reduce these boundary value problems to standard mathematical formulations with equal numbers of partial differential equations and boundary conditions. It is demonstrated that these formulations have some attractive features which appreciably facilitate their finite element discretizations. A numerical example involving scattering of plane electromagnetic waves from a perfect conducting thin plate illustrates the discussion
Keywords: analysis; partial; conditions; boundary; conducting; differential; discretizations; mathematical; element; EM; equations; equations; boundary; equations; boundary-value; equations; perfect; example; partial; Maxwell's; plate; plane; problems; electromagnetic; problems; finite; scattering; finite; scattering; Maxwell; structure; numerical; thin; value; wave

Pagoda: A Model for Autonomous Learning in Probabilistic Domains - desJardins, Marie (AI Magazine, 1993)
My Ph.D. dissertation describes PAGODA (probabilistic autonomous goal-directed agent), a model for an intelligent agent that learns autonomously in domains containing uncertainty. The ultimate goal of this line of research is to develop intelligent problem-solving and planning systems that operate in complex domains, largely function autonomously, use whatever knowledge is available to them, and learn from their experience. PAGODA was motivated by two specific requirements: The agent should be capable of operating with minimal intervention from humans, and it should be able to cope with uncertainty (which can be the result of inaccurate sensors, a nondeterministic environment, complexity, or sensory limitations). I argue that the principles of probability theory and decision theory can be used to build rational agents that satisfy these requirements.

Performance comparison of three modern DBMS architectures - Delis,A.; Roussopoulos, Nick (IEEE Transactions on Software Engineering, 1993)
The introduction of powerful workstations connected through local area networks (LANs) inspired new database management system (DBMS) architectures that offer high performance characteristics. The authors examine three such software architecture configurations: client-server (CS), the RAD-UNIFY type of DBMS (RU), and enhanced client-server (ECS). Their specific functional components and design rationales are discussed. Three simulation models are used to provide a performance comparison under different job workloads. Simulation results show that the RU almost always performs slightly better than the CS, especially under light workloads, and that ECS offers significant performance improvement over both CS and RU. Under reasonable update rates, the ECS over CS (or RU) performance ratio is almost proportional to the number of participating clients (for less than 32 clients). The authors also examine the impact of certain key parameters on the performance of the three architectures and show that ECS is more scalable that the other two
Keywords: client-server; Computational modeling; Computer architecture; database management systems; DBMS architectures; design rationales; functional components; Indexes; Local area networks; Military computing; Packaging; Performance analysis; performance evaluation; RAD-UNIFY type; simulation models; simulation results; Software architecture; software architecture configurations; software engineering; Throughput; Workstations

The processing of form documents - David Doermann; Rosenfeld, A. (Document Analysis and Recognition, 1993., Proceedings of the Second International Conference on, 1993)
An overview of an approach to the generic modeling and processing of known forms is presented. The system provides a methodology by which models are generated from regions in the document based on their usage. Automatic extraction of an optimal set of features to be used for registration is proposed, and it is shown how specialized detectors can be designed for each feature based on their position, orientation and width properties. Registration of the form with the model is accomplished using probing to establish correspondence. Form components which are corrupted by markings are detected and isolated, the intersections are interpreted and the properties of the non-form markings are used to reconstruct the strokes through the intersections. The feasibility of these ideas is demonstrated through an implementation of key components of the system
Keywords: AUTOMATIC; business; detectors; document; documents; extraction; feature; form; forms; generation; generic; handling; known; markings; model; modeling; non-form; optimal; properties; reconstruction; set; specialized; stroke; width

Query mapping and transformation techniques for problem solving with multiple knowledge servers - Raschid, Louiqa; Chang,Y.; Dorr, Bonnie J (Proceedings of the Second International Conference on Information and Knowledge Management (CIKM-93), 1993)
This paper describes a technique for infor-mation mediation when multiple heterogeneous knowl- edge and data servers are to be accessed during query processing. One problem is building an intelligent in- terface between each knowledge server (KS) and its processor (KP); and the second is to provide interoper- ability among multiple KP/KS so that a query may be answered using information from multiple sources. We present example scenarios which highlight these prob- lems and then outline query mapping and transforma- tion techniques that are applicable. The techniques for solving the interoperability problems involve rep- resentations in some canonical form. This includes a canonical representation (CR) corresponding to each KP/KS pair and a merged CR (MCR) to represent the mapping among the CRs. The MCR and CRs include relevant information obtained from a source query, and heterogeneous mapping (het-map) information, for all possible mappings among the multiple servers. The knowledge in the canonical form must be represented so that it can be easily accessed during query transfor- mation. We use an example of translating queries from an object schema to a relational schema to illustrate typical knowledge that must be represented in some canonical form. We use a high level logical language, F-logic, to represent the heterogeneous mapping (het- map) and query transformation information as a set of declarative rules, in the canonical form.

RF scattering and radiation by using a decoupled Helmholtz equation approach - D'Angelo,J.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 1993)
A novel finite-element formulation for the solution of 3-D RF scattering and radiation problems is presented. This formulation is based on the solution of a set of decoupled Helmholtz equations for the Cartesian components of the field vectors. This results in a robust, computer-efficient method that eliminates previous difficulties associated with `curl-curl' type partial differential equations. Although it is presented in the frequency domain, the method is easily extendible to the time domain
Keywords: 3D; analysis; approach; computer-efficient; computing; decoupled; domain; electrical; electromagnetic; element; engineering; equation; finite; finite-element; formulation; Frequency; frequency-domain; Helmholtz; method; Physics; problems; propagation; radiation; radiowave; RF; scattering; wave

SOCAP: lessons learned in automating military operations planning - Desimone,R.; Wilkins,D. E.; Bienkowski,M.; desJardins, Marie (Proceedings of the 6th international conference on Industrial and engineering applications of artificial intelligence and expert systems, 1993)

Use of lexical conceptual structure for intelligent tutoring - Dorr, Bonnie J; Hendler,J.; Blanksteen,S.; Migdalof,B. (University of Maryland, 1993)
We describe the use of an LCS-based semantics for question-answeringexercises in foreign language training. We start by reviewing the LCS model and show how this representation can be used to support a question answering lesson as well as a limited domain discourse. An authoring tool for entering the relevant semantic knowledge is also described.

Workshop summary: AAAI-92 Workshop on Constraining Learning with Prior Knowledge - desJardins, Marie (ACM SIGART Bulletin, 1993)

Active egomotion estimation: a qualitative approach - Aloimonos, J.; Duric, Z. (Computer Vision—ECCV'92, 1992)

Anthropomorphism: from Eliza to Terminator 2 - Don,Abbe; Brennan,Susan; Laurel,Brenda; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems, 1992)

Behavioral Visual Motion Analysis," - Aloimonos, J.; Duriç,Z.; Fermüller, Cornelia; Huang, L.; Rivlin,E.; Sharma, R. (Proceedings, DARPA Image Understanding Workshop, 1992)

Building a lexicon for machine translation: use of corpora for aspectual classification of verbs - Dorr, Bonnie J; Lee,Ki (University of Maryland at College Park, 1992)

A competitive distribution theory of neocortical dynamics - Reggia, James A.; D'Autrechy,C. L; Sutton III,G. G.; Weinrich,M. (Neural Computation, 1992)

Constraining MT divergences: spatial relations in the lexicon and knowledge base - Dorr, Bonnie J; Voss,Clare (University of Maryland at College Park, 1992)

Experiments on the concurrent rule execution in database systems - Delis,A.; Raschid, Louiqa; Sellis,T. (Tools with Artificial Intelligence, 1992. TAI'92, Proceedings., Fourth International Conference on, 1992)

Ground and airborne localization over rough terrain using random environmental range-measurements - Yacoob,Yaser; Davis, Larry S. (Pattern Recognition, 1992. Vol. I. Conference A: Computer Vision and Applications, Proceedings., 11th IAPR International Conference on, 1992)

Instrument Grasp: AModel and its Effects on Handwritten Strokes - David Doermann; Varma,V.; Rosenfeld, A. (University of Maryland, College Park, 1992)

Lateral cortical inhibition without lateral inhibitory connections - Reggia, James A.; Sutton,G.; D'Autrechy,C. L; Weinrich,M. (Neural Networks, 1992. IJCNN., International Joint Conference on, 1992)
The authors consider how a set of neurons forming a cortical column, none of which individually can competitively distribute its activity, can function collectively to produce competitive distribution of activation. To address this issue, they describe a model cortical column composed of three populations of excitatory neurons that collectively distribute their activity competitively. The idea of competitive distribution and the neural circuitry that could bring it about are described. Computer simulation results, implications, and testable predictions of the theory are presented
Keywords: brain models; competitive distribution of activation; digital simulation; excitatory neurons; lateral cortical inhibition; neural circuitry; neurophysiology; physiological models

Modeling of a Grasp for Handwriting - Varma,V.; David Doermann (Proceedings of the Twenty-Third Annual Modeling and Simulation Conference, 1992)

Parameterization of the interlingua in machine translation - Dorr, Bonnie J (Proceedings of the 14th conference on Computational linguistics - Volume 2, 1992)
The task of designing as interlingual machine translation system is difficult, first because the designer must have a knowledge of the principles underlying crosslinguistic distinctions for the languages under consideration, and second because the designer must then be able to incorporate this knowledge effectively into the system. This paper provides a catalog of several types of distinctions among Spanish, English, and German, and describes a parametric approach that characterizes these distinctions, both at the syntactic level and at the lexical-semantic level. The approach described here is implemented in a system called UNITRAN, a machine translation system that translates English, Spanish, and German bidirectionally.

A parameterized approach to integrating aspect with lexical-semantics for machine translation - Dorr, Bonnie J (Proceedings of the 30th annual meeting on Association for Computational Linguistics, 1992)
This paper discusses how a two-level knowledge representation model for machine translation integrates aspectual information with lexical-semantic information by means of parameterization. The integration of aspect with lexical-semantics is especially critical in machine translation because of the lexical selection and aspectual realization processes that operate during the production of the target-language sentence: there are often a large number of lexical and aspectual possibilities to choose from in the production of a sentence from a lexical semantic representation. Aspectual information from the source-language sentence constrains the choice of target-language terms. In turn, the target-language terms limit the possibilities for generation of aspect. Thus, there is a two-way communication channel between the two processes. This paper will show that the selection/realization processes may be parameterized so that they operate uniformly across more than one language and it will describe how the parameter-based approach is currently being used as the basis for extraction of aspectual information from corpora.

PARTI primitives for unstructured and block structured problems - Sussman, Alan; Saltz, J.; Das,R.; Gupta,S.; Mavriplis,D.; Ponnusamy,R.; Crowley,K. (Computing Systems in Engineering, 1992)
This paper describes a set of primitives (PARTI) developed to efficiently execute unstructured and block structured problems on distributed memory parallel machines. We present experimental data from a three-dimensional unstructured Euler solver run on the Intel Touchstone Delta to demonstrate the usefulness of our methods.

A randomized algorithm for slope selection - Dillencourt,M. B; Mount, Dave; Netanyahu,N. S (International Journal of Computational Geometry and Applications, 1992)

Recovery of temporal information from static images of handwriting - David Doermann; Rosenfeld, A. (Proceedings in the IEEE CVPR, 1992)
The problem of off-line handwritten character recognition has eluded a satisfactory solution for several decades. Researchers working in the area of on-line recognition have had greater success, but the possibility of extracting on-line information from static images has not been fully explored. The experience of forensic document examiners assures us that in many cases, such information can be successfully recovered.We outline the design of a system for the recovery of temporal information from static handwritten images. We provide a taxonomy of local, regional and global temporal clues which are often found in hand-written samples, and describe methods for recovering these clues from the image. We show how this system can benefit from obtaining a comprehensive understanding of the handwriting signal and a detailed analysis of stroke and sub-stroke properties. We suggest that the recovery task requires that we break away from traditional thresholding and thinning techniques, and we provide a framework for such analysis. We demonstrate how isolated temporal clues can reliably be extracted from this framework and propose a control structure for integrating the partial information. We show how many seemingly ambiguous situations can be resolved by the derived clues and our knowledge of the writing process, and provide several examples to illustrate our approach. The support of this research by the Ricoh Corporation is gratefully acknowledged.

Reflecting time in generated text: tense, aspect and temporal connecting words - Dorr, Bonnie J; Gaasterland,Terry (University of Maryland at College Park, 1992)

Simulating Pressure Variations in Handwriting - David Doermann; Varma,V. (Proceedings of the Twenty-Third Annual Modeling and Simulation Conference, 1992)

Software approaches to segmentation analysis - D'Autrechy,C. L; Reggia, James A.; Berndt,R. S (Computer Science Technical Report Series; Vol. CS-TR-2991, 1992)

Temporal clues in handwriting - David Doermann; Rosenfeld, A. (Pattern Recognition, 1992. Vol.II. Conference B: Pattern Recognition Methodology and Systems, Proceedings., 11th IAPR International Conference on, 1992)
Handwritten character recognition is typically classified as online or offline depending on the nature of the input data. Online data consists of a temporal sequence of instrument positions while offline data is in the form of a 2D image of the writing sample. Online recognition techniques have been relatively successful but have the disadvantage of requiring the data to be gathered during the writing process. This paper presents work on the extraction of temporal information from static images of handwriting and its implications for character recognition
Keywords: character; extraction; feature; handwriting; information; offline; online; recognition; techniques; temporal

A two-level knowledge representation for machine translation: Lexical semantics and tense/aspect - Dorr, Bonnie J (Lexical Semantics and Knowledge RepresentationLexical Semantics and Knowledge Representation, 1992)
This paper proposes a two-level model that integrates contemporary theories of tense and aspect with lexical semantics. The model is intended to be extensible to realms outside of the temporal domain (e.g., the spatial domain). The integration of tense and aspect with lexical-semantics is especially critical in machine translation because of the lexical selection process during generation: there is often a number of lexical connective and tense/aspect possibilities that may be produced from a lexical semantic representation, which, as defined in the model presented here, is largely underspecified. Temporal/aspectual information from the source-language sentence constrains the choice of target-language terms. In turn, the target-language terms limit the possibilities for generation of tense and aspect. Thus, there is a two-way communication channel between the two processes.

The use of lexical semantics in interlingual machine translation - Dorr, Bonnie J (Machine Translation, 1992)
This paper describes the lexical-semantic basis for UNITRAN, an implemented scheme for translating Spanish, English, and German bidirectionally. Two claims made here are that the current representation handles many distinctions (or divergences ) across languages without recourse to language-specific rules and that the lexical-semantic framework provides the basis for a systematic mapping between the interlingua and the syntactic structure. The representation adopted is an extended version of lexical conceptual structure which is suitable to the task of translating between divergent structures for two reasons: (1) it provides an abstraction of language-independent properties from structural idiosyncrasies; and (2) it is compositional in nature. The lexical-semantic approach addresses the divergence problem by using a linguistically grounded mapping that has access to parameter settings in the lexicon. We will examine a number of relevant issues including the problem of defining primitives, the issue of interlinguality, the cross-linguistic coverage of the system, and the mapping between the syntactic structure and the interlingua. A detailed example of lexical-semantic composition will be presented.

Conceptual Basis of the Lexicon in Machine Translation - Dorr, Bonnie J (Lexical acquisition: exploiting on-line resources to build a lexiconLexical acquisition: exploiting on-line resources to build a lexicon, 1991)

Data parallel algorithms for the numerical modeling of semiconductor devices - Darling,J. P.; Mayergoyz, Issak D (Proceedings of the 5th SIAM Conference on Parallel Processing for Scientific Computing, 1991)

Lexical semantics and tense/aspect in machine translation - Dorr, Bonnie J (University of Maryland at College Park, 1991)

Machine translation: A principle-based approach - Dorr, Bonnie J (Artificial intelligence at MIT expanding frontiers, 1991)

Modern client-server DBMS architectures - Roussopoulos, Nick; Delis,Alexis (ACM SIGMOD RecordSIGMOD Rec., 1991)

Recovery of Temporal Information from Static Images of Handwriting - David Doermann; Rosenfeld, A. (Center for Automation Research, University of Maryland, 1991)
The problem of off-line handwritten character recognition has eluded a satisfactory solution for several decades. Researchers working in the area of on-line recognition have had greater success, but the possibility of extracting on-line information from static images has not been fully explored. The experience of forensic document examiners assures us that in many cases, such information can be successfully recovered.We outline the design of a system for the recovery of temporal information from static handwritten images. We provide a taxonomy of local, regional and global temporal clues which are often found in hand-written samples, and describe methods for recovering these clues from the image. We show how this system can benefit from obtaining a comprehensive understanding of the handwriting signal and a detailed analysis of stroke and sub-stroke properties. We suggest that the recovery task requires that we break away from traditional thresholding and thinning techniques, and we provide a framework for such analysis. We demonstrate how isolated temporal clues can reliably be extracted from this framework and propose a control structure for integrating the partial information. We show how many seemingly ambiguous situations can be resolved by the derived clues and our knowledge of the writing process, and provide several examples to illustrate our approach. The support of this research by the Ricoh Corporation is gratefully acknowledged.

Solving divergences in machine translation - Dorr, Bonnie J (University of Maryland at College Park, 1991)

Using thematic roles for lexical-semantic composition in machine translation - Dorr, Bonnie J (University of Maryland at College Park, 1991)

The advantages of hypertext for large information spaces; where are the big systems? - Shneiderman, Ben; Deter,R. (Hypertext: concepts, systems and applications: proceedings of the First European Conference on Hypertext, INRIA, France, November 1990, 1990)

Connectionist models and information retrieval - Doszkocs,T. E; Reggia, James A.; others (Annual review of information science and technology, 1990)

A Cross-Linguistic Approach to Translation - Dorr, Bonnie J (Proceedings of the Third International Conference on Theoretical and Methodological Issues in Machine Translation of Natural Language, 1990)

Lexical conceptual structure and machine translation - Dorr, Bonnie J (Massachusetts Institute of Technology, 1990)

Mailpiece Preprocessing: The population of Character Parts - David Doermann; Rosenfeld, A. (ATC, 1990)

Parallel algorithm for the solution of nonlinear poisson equation of semiconductor device theory and its implementation on the IVIPP - Darling,J. P.; Mayergoyz, Issak D (Journal of Parallel and Distributed Computing, 1990)
The solution of the nonlinear Poisson equation of semiconductor device theory is important for the design of submicron devices used in VLSI circuits. The conventional technique applied for the solution of this equation is based on the application of Newton's method to simultaneous discretized equations. This technique requires large computational and storage capacities to handle the fine meshes associated with the modeling of submicron semiconductor devices. A new algorithm for the numerical solution of this equation has recently been developed. One advantage that this algorithm has over conventional techniques is that it is inherently parallel, and is thus well suited to implementation on a computer with large parallelism. This paper describes the initial implementation and testing of this algorithm on NASA's Massively Parallel Processor (MPP).

Parsimonious covering theory in cognitive diagnosis and adaptive instruction - Reggia, James A.; D'Autrechy,C. L (Diagnostic Monitoring of Skill and Knowledge AcquisitionDiagnostic Monitoring of Skill and Knowledge Acquisition, 1990)

Solving thematic divergences in machine translation - Dorr, Bonnie J (Proceedings of the 28th annual meeting on Association for Computational Linguistics, 1990)
Though most translation systems have some mechanism for translating certain types of divergent predicate-argument structures, they do not provide a general procedure that takes advantage of the relationship between lexical-semantic structure and syntactic structure. A divergent predicate-argument structure is one in which the predicate (e.g., the main verb) or its arguments (e.g., the subject and object) do not have the same syntactic ordering properties for both the source and target language. To account for such ordering differences, a machine translator must consider language-specific syntactic idiosyncrasies that distinguish a target language from a source language, while making use of lexical-semantic uniformities that tie the two languages together. This paper describes the mechanisms used by the UNITRAN machine translation system for mapping an underlying lexical-conceptual structure to a syntactic structure (and vice versa), and it shows how these mechanisms coupled with a set of general linking routines solve the problem of thematic divergence in machine translation.

Dynamic bin packing problem - Dikshit,Piyush; Guimaraes,Katia; Ramamurthy,Maya; Agrawala, Ashok K.; Larsen,Ronald L (SIAM Journal on Computing, 1989)
In a previous work we have defined a general architecture model for autonomous systems, which can be mapped easily to describe the functions of any automated system (SDAG-86-01). In this note, we use the model to describe the problem of thermal management in space stations. First we briefly review the architecture, then we present the environment of our application, and finally we detail the specific function for each functional block of the architecture for that environment.

Parallel plan execution with self-processing networks - D'Autrechy,C. L; Reggia, James A. (Telematics and Informatics, 1989)

Parsimonious covering as a method for natural language interfaces to expert systems* 1 - Dasigi,V. R; Reggia, James A. (Artificial Intelligence in Medicine, 1989)

A general-purpose simulation environment for developing connectionist models - D'Autrechy,C. L; Reggia, James A.; Sutton,G. G; Goodall,S. M (Simulation, 1988)

A Lexical Conceptual Approach to Generation for Machine Translation - Dorr, Bonnie J (MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB, 1988)
Current approaches to generation for machine translation make use of direct-replacement templates, large grammars, and knowledge-based inferencing techniques. Not only are rules language-specific, but they are too simplistic to handle sentences that exhibit more complex phenomena. Furthermore, these systems are not easily extendable to other languages because the rules that map the internal representation to the surface form are entirely dependent on both the domain of the system and the language being generated. Finally an adequate interlingual representation has not yet been discovered; thus, knowledge-based inferencing is necessary and syntactic cross-linguistic generalization cannot be exploited. This report introduces a plan for the development of a theoretically based computational scheme of natural language generation for a translation system. The emphasis of the project is the mapping from the lexical conceptual structure of sentences to an underlying or base syntactic structure called deep structure. This approach tackles the problems of thematic and structural divergence, i.e., it allows generation of target language sentences that are not thematically or structurally equivalent to their conceptually equivalent source language counterparts. Two other more secondary tasks, construction of a dictionary and mapping from deep structure to surface structure, will also be discussed. The generator operates on a constrained grammatical theory rather than on a set of surface level tranformations.
Keywords: *MACHINE TRANSLATION; *NATURAL LANGUAGE; *SYSTEMS APPROACH; COMPUTATIONS; CYBERNETICS; Dictionaries; grammars; internal; LEXICOGRAPHY; SURFACES; syntax; THEORY; TRANSLATIONS; WORDS(LANGUAGE)

The Maryland approach to image understanding - Aloimonos, J.; Davis, Larry S.; Rosenfeld, A. (Science Applications International Corp, Proceedings: Image Understanding Workshop,, 1988)

UNITRAN: A PRINCIPLE-BASED PARSER FOR MACHINE TRANSLATION - Dorr, Bonnie J (The MIT parsing volume, 1987-88, 1988)

Fine and Medium Grained Parallel Algorithms for Matrix QR Factorization - O'Leary, Dianne P. (Algorithms and Applications on Vector and Parallel ComputersAlgorithms and Applications on Vector and Parallel Computers, 1987)

Life on a desert island - Drapkin,J.; Miller,M.; Perlis, Don (Proc. Workshop on The Frame Problem in Artificial Intelligence, 1987)

Principle-Based Parsing for Machine Translation - Dorr, Bonnie J (MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB, 1987)
Many syntactic parsing strategies for machine translation systems are based entirely on context-free grammars. These parsers require an overwhelming number of rules; thus, translation systems using rule-based parsers either have limited linguistic coverage, or they have poor performance due to formidable grammar size. This report shows how a principle-based parser with a co-routine design improves parsing for translation. The parser consists of a skeletal structure-building mechanism that operates in conjunction with a linguistically based constraint module, passing control back and forth until a set of underspecified skeletal phrase-structures is converted into a fully instantiated parse tree. The modularity of the parsing design accommodates linguistic generalization, reduces the grammar size, allows extension to other languages, and is compatible with studies of human language processing. Keywords: Natural language processing, Interlingual translation, Parsing, Subroutines, Principles vs. Rules, Co-routine design, Linguistic constraints.
Keywords: *MACHINE TRANSLATION; *PARSERS; *SYNTAX; CONTROL; COROUTINE DESIGN; CYBERNETICS; grammars; HUMANS; LANGUAGE; linguistics; MODULAR CONSTRUCTION; natural language; PRINCIPLES BASED PARSERS; PROCESSING; STRATEGY; SUBROUTINES

Representations Based on Triangular Grids - De Floriani, Leila (The Vkual Computer, 1987)

UNITRAN: an interlingual approach to machine translation - Dorr, Bonnie J (Proceedings of the Sixth Conference of the American Association of Artificial Intelligence, 1987)
Machine translation has been a particularly difficult problem in the area of Natural Language Processing for over two decades. Early approaches to translation failed in part because interaction effects of complex phenomena made translation appear to be unmanageable. Later approaches to the problem have succeeded but are based on many language-specific rules. To capture all natural language phenomena, rule-based systems require an overwhelming number of rules; thus, such translation systems either have limited coverage, or poor performance due to formidable grammar size. This paper presents an implementation of an "interlingual" approach to natural language translation. The UNITRAN system relies on principle-based descriptions of grammar rather than rule-oriented descriptions. The model is based on linguistically motivated principles and their associated parameters of variation. Because a few principles cover all languages, the unmanageable grammar size of alternative approaches is no longer a problem.

A preliminary excursion into step-logics - Drapkin,J.; Perlis, Don (Proceedings of the ACM SIGART international symposium on Methodologies for intelligent systems -, 1986)

Step-logics: An alternative approach to limited reasoning - Drapkin,J.; Perlis, Don (Proceedings of the European Conf. on Artificial Intelligence, 1986)

Expert systems based on set covering model - Reggia, James A.; Dana,S. N.; Pearl,Y. W. (International Journal on Man-Machine Studies, 1983)

Transcription of cloned tRNA and 5S RNA genes in a Drosophila cell free extract - Dingermann,Theodor; Sharp,Stephen; Appel,Bernd; DeFranco,Donald; Mount, Stephen M.; Heiermann,Reinhard; Pongs,Olaf; Söll,Dieter (Nucleic Acids ResearchNucl. Acids Res., 1981)
We describe the preparation of a cell-free extract from Drosophila Kc cells which allows transcription of a variety of cloned eukaryotic RNA polymerase III genes. The extract has low RNA-processing nuclease activity and thus the major products obtained are primary transcripts.

Approximate pattern matching in a pattern database system - Davis, Larry S.; Roussopoulos, Nick (Information Systems, 1980)
This work is concerned with the organization of a large database of binary pictures (normalized for size, rotation and position) and with the efficient "inexact match" of an input pattern against the whole database. Current techniques in pattern analysis use matching algorithms without any regard to the global organization of the storage representations of the models they are to match. Consequently, the algorithms are only practical for small databases. This paper discusses the design of a pattern database system and the economy that it provides for the matching problem. The database organization is based on the quad-tree representation of binary patterns. Given an arbitrary decomposition D (or partition) of a pattern P and an arbitrary function f on the pattern, we repeatedly apply f on D(P), D(D(P))P, ... to obtain higher and higher levels of abstraction f(D)(P)), f(D(D(P))), ... of the pattern. The computed values obtained after the jth application of f are used to label the ith level of the pyramid. The specific representation used in this paper is called the sum-quad-tree, in which each level of the tree stores the sum of the labels of its sons. The lowest level of the sum-quad-tree corresponds to the individual pixels and is the nth level (i.e. node m at level n implies v(m) = 0 or v(m) = 1). Nodes at the jth level of the sum-quad-tree correspond to sums of 2n-j × 2n-j picture points, so that the 0th level contains the number of 1's in the pattern. The pyramid representation is used as a hierarchical (n-level) indexing scheme of the database. The advantage of this organization is that the matching algorithms presented reject most of the patterns in the database by utilizing the relatively small in size index tables and thus avoid the overhead of unnecessary CPU time and operation between main memory and secondary storage.

An experiment using memorization/reconstruction as a measure of programmer ability - Di Persio,Tom; Isbister,Dan; Shneiderman, Ben (International Journal of Man-Machine Studies, 1980)
Measuring the abilities of programmers in a classroom or organizational setting is not a trivial task. Current approaches are not always accurate or reliable. This paper describes an experiment which provides evidence that performance on a memorization/recon- struction test can be used as a measure or predictor of programmer ability. The contribution of indentation in program comprehension is also examined.

Linear programming Problems Arising from Partial Differential Equations - O'Leary, Dianne P. (Sparse Matrix Proceedings 1978Sparse Matrix Proceedings 1978, 1979)

A Method for Organizing a Project Network into a Tree Structure - De Floriani, Leila (Third Symposium on Operations Research, Mannheim University, Tagungsbericht, 1978)