The Standard Generalized Markup Language (SGML) and the Extensible Markup Language (XML) allow users to define document type definitions (DTDs), which are essentially extended context-free grammars expressed in a notation that is similar to extended Backus-Naur form. The right-hand side of a production, called a content model, is both an extended and a restricted regular expression. The semantics of content models for SGML DTDs can be modified by exceptions (XML DTDs do not allow exceptions). Inclusion exceptions allow named elements to appear anywhere within the content of a content model, and exclusion exceptions preclude named elements from appearing in the content of a content model.
We give precise definitions of the semantics of exceptions, and prove that they do not increase the expressive power of SGML DTDs when we restrict DTDs according to accepted practice. We prove the following results:
A finite-state machine is called a Thompson machine if it can be constructed from a regular expression using Thompson's construction. We call the underlying digraph of a Thompson machine a Thompson digraph. We characterize Thompson digraphs and, as one application of the characterization, we give an algorithm that generates an equivalent regular expression from a Thompson machine in time linear in the number of states. Although the construction is simple, it is novel in that the usual constructions of equivalent regular expressions from finite-state machines produce regular expressions that have size exponential in the size of the given machine, in the worst case. The construction provides a first step in the construction of small expressions from finite-state machines.
A finite-state machine is called a Thompson machine if it can be constructed from a regular expression using Thompson's construction. We assign distinct bracket pairs to the source and target states of all machine units that make up a Thompson machine. Each path from the start state to the final state of such a Thompson machine spells out a Dyck string. The collection of all such Dyck strings is the Thompson language of the given machine and the collection of such strings that are spelled out by simple paths is the simple Thompson language of the given machine. We characterize simple Thompson languages and Thompson languages, and we investigate their relationship.
A finite-state machine is called a Thompson machine if it can be constructed from a regular expression using Thompson's construction. We call the underlying digraph of a Thompson machine a Thompson digraph. We establish and prove a characterization of Thompson digraphs. As one application of the characterization, we give an algorithm that generates an equivalent regular expression from a Thompson machine in time linear in the number of states.
Map labeling in geographic information systems has been considered to be important and well studied by the cartographic and computer science researchers [][][]. In recent papers [][][], the problem of labeling a rectilinear map was studied. A rectilinear map consists of a set of n mutually non-intersecting rectilinear (horizontal or vertical) line segments, and each segment is allowed to use a rectangular label of height B and length the same as the segment. A label can be placed at one of three positions, thus the problem is called the 3-position rectilinear segment labeling problem. As a generalization of the 3-position labeling problem, k-position problem, k >= 1, was also studied in several literatures.
Van Kreveld, Strijk and Wolff [] introduced the notion of sliding labels, where labels are not restricted to three (or any finite number of) predefined positions but can slide and be placed at any position as long as it intersects the object.In [], they labeled p oints with sliding labels and introduced three different models of point labeling with sliding labels depending on the number of label sides allowed to touch points. Maximizing the number of points labeled was their objective, and they showed that the problem is NP-complete under the most general model of sliding labeling. A simple and efficient (1)/(2)-factor approximation algorithm was given.
In this paper, we will consider labeling rectilinear maps with sliding rectangular labels, i.e, the infty-position rectilinear segment labeling problem will be considered. Unlike van Kreveld, Strijk and Wolff [], our objective is to maximize the height of labels. Depending on the type of input segments, three different versions are possible.
In this paper efficient algorithms for the optimizations of these three problems will be given. For Problem 1D, a linear time algorithm is sufficient to solve it, after sorting the segments according to their y-coordinates. We next show that Problem 2D can be solved in a quadratic time. For Problem HV, we present a polynomial time "exact" algorithm and faster constant factor approximation algorithms.
In this paper, we consider problems of placing two equiradial disks in a convex polygon so that they are non-overlapping. Our goal is to maximize the radius of the disks. These problems are well motivated from gift wrapping problems that determine whether a gift is wrapped up (or hidden) using a given paper through one-straight fold. We also present efficient algorithms for several variants.
In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the previously added gates. The depth of the new gate is defined to be one more than the maximal depth of its input gates. We show that the expected depth of a random circuit with n gates is bounded from above by e f lnn and from below by 2.04...f lnn.
Milling is the mechanical process of removing material from a piece of stock through the use of a rapidly spinning circular milling tool in order to form some desired geometric shape. An important problem in computer-aided design and manufacturing is the automated generation of efficient milling plans for computerized numerically controlled (CNC) milling machines. Among the most common milling problems is simple 2-dimensional pocket milling: cut a given 2-dimensional region down to some constant depth using a given set of milling tools. Most of the research in this area has focused on generating such milling plans assuming that the machine has a tool of a single size. Since modern CNC milling machines typically have access to a number of milling tools of various sizes and the ability to change tools automatically, this raises the important optimization problem of generating efficient milling plans that take advantage of this capability to reduce the total milling time.
We consider the following multiple-tool milling problem: Given a region in the plane and a set of tools of different sizes, determine how to mill the desired region with minimum cost. The problem is known to be NP-hard even when restricted to the case of a single tool. In this paper, we present a polynomial-time approximation algorithm for the multiple-tool milling problem. The running time and approximation ratio of our algorithm depend on the simple cover complexity (introduced by Mitchell, Mount, and Suri) of the milling region.
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and eps> 0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance epsw of the boundary of Q either may or may not be counted. We show that in any fixed dimension d, a set of n points in Rd can be preprocessed in O(nlogn) time and O(n) space, such that approximate queries can be answered in O(logn + (1/eps)d) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O(logn + (1/eps)d-1) time. We also present a lower bound for approximate range searching based on partition trees of Omega(logn + (1/eps)d-1), which implies optimality for convex ranges (assuming fixed dimensions). Finally we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.
We propose a class of abstract Voronoi diagrams in 3-space that generalizes the planar abstract Voronoi diagram of Klein. Our class of abstract Voronoi diagrams includes the Voronoi diagram of point sites in general position under any convex distance function. To characterize the abstract Voronoi diagram in 3-space we introduce the notion of intersection characteristic. We determine the intersection characteristic for the simplex, the Linfty, and the Lp distance function. We find that the intersection characteristic in case of the simplex distance function is similar to that of the usual Euclidean distance. This enables us to give a randomized incremental algorithm for computing the Voronoi diagram under the simplex distance function in quadratic expected time.
In this paper we refine upper and lower bounds for the channel capacity of a serial, binary rewritable medium in which no two consecutive locations may store `1's and no consecutive locations may be altered in a single rewriting pass. This problem was originally examined by Cohn [] who proved that C, the channel capacity of the memory, in bits per symbol per rewrite, satisfies 0.50913... <= C <= 0.56029.... In this paper we show how to model the problem as a constrained two-dimensional binary matrix problem and then modify recent techniques for dealing with such matrices to derive improved bounds of 0.53500... <= C <= 0.55209.... Key words: capacity, channel graph, eigenvalue, two-dimensional codes, runlength-limited codes, constrained arrays.
We consider the problem of finding a k-median in a directed tree. We present an algorithm that computes a k-median in O(Pk2) time where k is the number of resources to be placed and P is the path length of the tree. In the case of a balanced tree, this implies O(k2 n logn) time, in a random tree O(k2 n3/2), while in the worst case O(k2 n2). Our method employs dynamic programming and uses O(n k) space, while the best known algorithms for undirected trees require O(n2 k) space.
Keywords: Algorithms, Analysis of Algorithms, Combinatorial Problems, Dynamic Programming, k-Median Problem.
We consider problems of finding an optimal bridge (p,q) between two polygons P and Q that minimizes the length of the longest path connecting two points on the boundaries of P and Q which passes through the bridge (p,q) to move from one polygon to the other. We propose efficient algorithms for three problems according to whether P and Q are convex or not. The convex-convex problem in which P and Q both are convex is solved in O(n+m) time, where n and m are the number of vertices of P and Q, respectively. The simple-convex problem is solved in O((n+m)log(n+m)) time, and the simple-simple problem is solved in O(nm + m logm) time for m >= n.
The algorithms developed can be easily extended to more general problems in which the goal is to find a bridge (p,q) that minimizes the length of the longest path connecting two points, each belonging to a point set given in P and in Q, which passes through the bridge (p,q). These general problems can be solved in the same time bounds as those in the problems above, only increasing a logn-factor when two polygons are convex.
These problems are motivated from the bridge construction between two islands or from the canal construction between two lakes.
In this paper we develop a method for determining the exact number of spanning trees in (directed or undirected) circulant graphs. Using this method we can, for any class of circulant graph, exhibit a recurrence relation for the number of its spanning trees. We describe the method and give examples of its use.
In this paper, we consider some variants of the two-center problems. Let P be a convex polygon with n vertices in the plane. We wan to find two congruent closed disks whose union covers P (its boundary and interior) and whose radius is minimized. We also consider its discrete version with centers restricted to be at some vertices of P. See Figure . Compared with the two-center problems for points, differences are that (1) points to be covered by two disks are the vertices of P in convex positions (not in arbitrary positions) and (2) two disks should cover the edges of P as well as its vertices. By points in convex positions, we mean that the points form the vertices of a convex polygon. (1) suggests our problems are most likely easier than the standard point-set two-center problems, but (2) tells us that they could be more difficult.
Our results are summarized as follows: