Search

We investigate the bend-minimization problem with respect to a new drawing style called an orthogonally convex drawing , which is an orthogonal drawing with an additional requirement that each inner face is drawn as an orthogonally convex polygon . For the class of biconnected plane graphs of maximum degree 3, we present a necessary and sufficient condition for the existence of a no-bend orthogonally convex drawing, which in turn, enables a linear time algorithm to check and construct such a drawing if one exists. We also develop a flow network formulation for bend-minimization in orthogonally convex drawings, yielding a polynomial time solution for the problem. An interesting application of our orthogonally convex drawing technique is to characterize internally triangulated plane graphs that admit floorplans using only orthogonally convex modules subject to given orthogonally convex boundary constraints. [ABSTRACT FROM AUTHOR]

An unfolding of a polyhedron is a single connected planar piece without overlap resulting from cutting and flattening the surface of the polyhedron. Even for orthogonal polyhedra, it is known that edge-unfolding, i.e., cuts are performed only along the edges of a polyhedron, is not sufficient to guarantee a successful unfolding in general. However, if additional cuts parallel to polyhedron edges are allowed, it has been shown that every orthogonal polyhedron of genus zero admits a grid-unfolding with quadratic refinement. Using a new unfolding technique developed in this paper, we improve upon the previous result by showing that linear refinement suffices. For 1-layer orthogonal polyhedra of genus , we show a grid-unfolding algorithm using only additional cuts, affirmatively answering an open problem raised in a recent literature. Our approach not only requires fewer cuts but yields much simpler algorithms. [ABSTRACT FROM AUTHOR]

A rectilinear dual of a plane graph refers to a partition of a rectangular area into nonoverlapping rectilinear polygonal modules, where each module corresponds to a vertex such that two modules have a side-contact iff their corresponding vertices are adjacent. An interesting observation is that most algorithms yielding low polygonal complexity rectilinear duals require the use of ⊤-shape modules or their extensions. To justify the intuition that ⊤-shape modules are more powerful than other 8-sided modules, we show the optimum polygonal complexity of ⊤-free rectilinear duals to be exactly 12. Our construction uses only monotone staircase modules. We continue this line of research by studying polygonal complexity and area-universality of rectilinear duals using modules of constrained shapes. Motivated by the design challenges in 3D IC technology, we also study the generalization of rectilinear duals in three dimensions by allowing each module to be an orthogonal polyhedron. Such a generalization to three dimensions opens the door for non-planar graphs to be accommodated in floorplan design. In particular, we prove that all chordal graphs admit 3D floorplans, which parallels the well-known result that all maximal plane graphs admit rectilinear duals. [ABSTRACT FROM AUTHOR]

A transducer is infinite-valued if the maximal number of different outputs for an input string is not bounded by any constant. For one-way finite transducers, sufficient and necessary conditions exist in terms of the structure of a transducer to characterize whether the transducer is infinite-valued or not, yielding the decidability result of the finite-valuedness problem. As crossing sequences in two-way automata often play similar roles as states in their one-way counterparts, we consider analogous criteria in the setting of crossing sequences to characterize the infinite-valuedness of two-way finite transducers. The characterization leads to a decidability proof for the valuedness problem of two-way finite transducers. [ABSTRACT FROM AUTHOR]

Abstract: We look at some classes of two-way transducers with auxiliary memory and investigate their containment and equivalence problems. We believe that our results are the strongest known to date concerning two-way transducers. [Copyright &y& Elsevier]

Abstract: The conventional force-directed methods for drawing undirected graphs are based on either vertex–vertex repulsion or vertex–edge repulsion. In this paper, we propose a new force-directed method based on edge–edge repulsion to draw graphs. In our framework, edges are modelled as charged springs, and a final drawing can be generated by adjusting positions of vertices according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by previous algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution and usually having larger average angular resolution. However, it should be noted that exhibiting a higher degree of symmetry and larger average angular resolution does not come without a price, as the new approach might result in the increase in undesirable overlapping of vertices as some of our experimental results indicate. To ease the problem of node overlapping, we also consider a hybrid approach which takes into account both edge–edge and vertex–vertex repulsive forces in drawing a graph. [Copyright &y& Elsevier]

Although randomization often increases the degree of flexibility in system design, analyzing system properties in the probabilistic framework introduces additional difficulties and challenges in comparison with their nonprobabilistic counterparts. In this paper, we focus on probabilistic versions of two problems frequently encountered in discrete event systems, namely, the reachability and forbidden-state problems. Our main concern is to see whether there exists a (or for every) non-blocking or fair control policy under which a given finite- or infinite-state system can be guided to reach (or avoid) a set of goal states with probability one. For finite-state systems, we devise algorithmic approaches which result in polynomial time solutions to the two problems. For infinite-state systems modelled as Petri nets, the problems are undecidable in general. For the class of persistent Petri nets, we establish a valuation approach through which the convergence behavior of a system is characterized, which in turn yields solutions to the reachability and forbidden-state problems. [ABSTRACT FROM AUTHOR]

Abstract: In a balloon drawing of a tree, all the children under the same parent are placed on the circumference of the circle centered at their parent, and the radius of the circle centered at each node along any path from the root reflects the number of descendants associated with the node. Among various styles of tree drawings reported in the literature, the balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. For each internal node in a balloon drawing, the ray from the node to each of its children divides the wedge accommodating the subtree rooted at the child into two sub-wedges. Depending on whether the two sub-wedge angles are required to be identical or not, a balloon drawing can further be divided into two types: even sub-wedge and uneven sub-wedge types. In the most general case, for any internal node in the tree there are two dimensions of freedom that affect the quality of a balloon drawing: (1) altering the order in which the children of the node appear in the drawing, and (2) for the subtree rooted at each child of the node, flipping the two sub-wedges of the subtree. In this paper, we give a comprehensive complexity analysis for optimizing balloon drawings of rooted trees with respect to angular resolution, aspect ratio and standard deviation of angles under various drawing cases depending on whether the tree is of even or uneven sub-wedge type and whether (1) and (2) above are allowed. It turns out that some are NP-complete while others can be solved in polynomial time. We also derive approximation algorithms for those that are intractable in general. [ABSTRACT FROM AUTHOR]

Abstract: Graphs with nonuniform nodes arise naturally in many real-world applications. Although graph drawing has been a very active research in the computer science community during the past decade, most of the graph drawing algorithms developed thus far have been designed for graphs whose nodes are represented as single points. As a result, it is of importance to develop drawing methods for graphs whose nodes are of different sizes and shapes, in order to meet the need of real-world applications. To this end, a potential field approach, coupled with an idea commonly found in force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. The crucial feature of our approach is that the rotation of every nonuniform node and the multiple edges between two nonuniform nodes are taken into account. In comparison with the existing algorithms found in the literature, our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of moderate-sized graphs in 2-D and 3-D can be produced reasonably efficiently. That is, our approach is suitable for moderate-sized interactive graphs or larger-sized static graphs. Furthermore, to illustrate the usefulness of our new drawing method for graphs with zero-sized nodes, we give an application to the visualization of hierarchical clustered graphs, for which our method offers a very efficient solution. [Copyright &y& Elsevier]

Abstract: Upward-closed sets of integer vectors enjoy the merit of having a finite number of minimal elements, which is behind the decidability of a number of Petri net related problems. In general, however, such a finite set of minimal elements may not be effectively computable. In this paper, we develop a unified strategy for computing the sizes of the minimal elements of certain upward-closed sets associated with Petri nets. Our approach can be regarded as a refinement of a previous work by Valk and Jantzen (in which a necessary and sufficient condition for effective computability of the set was given), in the sense that complexity bounds now become available provided that a bound can be placed on the size of a witness for a key query. The sizes of several upward-closed sets that arise in the theory of Petri nets as well as in backward-reachability analysis in automated verification are derived in this paper, improving upon previous decidability results shown in the literature. [Copyright &y& Elsevier]

The conventional forbidden state problem for discrete event systems is concerned with the issue of synthesizing a maximally permissive control policy to prevent a discrete event system from reaching any forbidden state during the course of its computation. In this paper, we regard the forbidden state problem as a decision problem, and investigate the decidability/complexity issue of the problem under two new types of control policies, namely, non-blocking and fair policies, for finite state systems and Petri nets. [ABSTRACT FROM AUTHOR]

Abstract: We look at a 1-membrane catalytic system with evolution rules of the form or , where C is a catalyst, a is a noncatalyst symbol, and is a (possibly null) string representing a multiset of noncatalyst symbols. (Note that we are only interested in the multiplicities of the symbols.) A catalytic system (CS) can be regarded as a language acceptor in the following sense. Given an input alphabet consisting of noncatalyst symbols, the system starts with an initial configuration wz, where is a fixed string of catalysts and noncatalysts not containing any symbol in z, and for some nonnegative integers , with . At each step, a maximal multiset of rules is nondeterministically selected and applied in parallel to the current configuration to derive the next configuration (note that the next configuration is not unique, in general). The string z is accepted if the system eventually halts. It is known that a 1-membrane CS is universal in the sense that any unary recursively enumerable language can be accepted by a 1-membrane CS (even by purely CSs, i.e., when all rules are of the form ). A CS is said to be deterministic if at each step there is a unique maximally parallel multiset of rules applicable. It has been an open problem whether deterministic systems of this kind are universal. We answer this question negatively. We show that the membership problem for deterministic CSs is decidable. In fact, we show that the Parikh map of the language accepted by any deterministic CS is a simple semilinear set which can be effectively constructed. Since nondeterministic 1-membrane CS acceptors (with two catalysts) are universal, our result gives the first example of a variant of P systems for which the nondeterministic version is universal, but the deterministic version is not. We also show that for a deterministic 1-membrane CS using only rules of type , the set of reachable configurations from a given initial configuration is an effective semilinear set. The application of rules of type , however, is sufficient to render the reachability set nonsemilinear. Our results generalize to multimembrane deterministic CSs. We also consider deterministic CSs which allow rules to be prioritized and investigate three classes of such systems, depending on how priority in the application of the rules is interpreted. For these three prioritized systems, we obtain contrasting results: two are universal and one only accepts semilinear sets. [Copyright &y& Elsevier]

Abstract: We investigate the problem of characterizing the solution spaces for timed automata augmented by unknown timing parameters (called timing parameter automata (TPA)). The main contribution of this paper is that we identify three non-trivial subclasses of TPAs, namely, upper-bound, lower-bound and bipartite TPAs, and analyze how hard it is to characterize the solution spaces. As it turns out, we are able to give complexity bounds for the sizes of the minimal (resp., maximal) elements which completely characterize the upward-closed (resp., downward-closed) solution spaces of upper-bound (resp., lower-bound) TPAs. For bipartite TPAs, it is shown that their solution spaces are not semilinear in general. We also extend our analysis to TPAs equipped with counters without zero-test capabilities. [Copyright &y& Elsevier]

We propose a novel valuation-based approach for analyzing conflict-free Petri nets. The basic idea is to associate a natural number, called the valuation, to each marking in the Petri net. If the set of markings of zero valuation is forward closed, then the valuation along any Petri net computation is nonincreasing, and in many cases, has the tendency to move towards zero valuation. Using the valuation-based method, we demonstrate a number of problems for conflict-free Petri nets to be decidable. [Copyright &y& Elsevier]

Abstract. A number of problems concerning priority conflict-free Petri nets are investigated in this paper. We show the teachability problem for such Petri nets to be NP-complete. (Using a similar technique, the NP-completeness result applies to the class of priority BPP-nets as well.) As for the boundedness problem, an NP-completeness result is demonstrated for priority conflict-free Petri nets with two types of prioritized transitions. (In contrast, the problem is known to be P-complete for conflict-free Petri nets without priorities.) We also investigate the home state problem, i.e., the problem of determining whether home states exist in a given a Petri net, for conflict-free Petri nets with and without priorities. As it turns out, home states always exist for bounded conflict-free Petri nets without priorities. If an additional liveness constraint is imposed, such Petri nets are guaranteed to be 'reversible' (i.e., their initial states are home states). For priority conflict-free Petri nets, being bounded and live is sufficient for the existence of home states. However, if the liveness assumption is dropped, the existence of home states is no longer guaranteed. [ABSTRACT FROM AUTHOR]

The aim of this paper is to develop a unified approach for deriving complexity results for problems concerning conflict-free Petri nets. To do so, we first define a class of formulas for paths in Petri nets. We then show that answering the satisfiability problem for conflict-free Petri nets is tantamount to solving a system of linear inequalities (which is known to be in P). Since a wide spectrum of Petri net problems (including various fairness-related problems) can be reduced to the satisfiability problem in a straightforward manner, our approach offers an umbrella under which many Petri net problems for conflict-free Petri nets can be shown to be solvable in polynomial time. As a side-product, our analysis provides evidence as to why detecting unboundedness for conflict-free Petri nets is easier (provided P ≠ NP) than for normal and sinkless Petri nets (which are two classes that properly contain conflict-free Petri nets). [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of one-tape linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider deterministically-chosen advice (not necessarily algorithmically determined) and randomly-chosen advice (according to certain probability distributions). In particular, we show that certain weak machines can be significantly enhanced in computational power when randomized advice is provided in place of deterministic advice. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate various decision problems concerning parameterized versions of some classes of machines. Let be the class of nondeterministic multitape Turing machine (TM) acceptors with a two-way read-only input, at most states, at most read–write worktapes, and at most symbols in the worktape alphabet, where are fixed positive integers. There is no restriction on the cardinality of the input alphabet. We are able to show the emptiness, disjointness, and universe (also called universality) problems to be decidable for . For the class consisting of machines in that always halt or whose minimal-time accepting computations can be bounded by some recursive function (where is the input length), the containment and equivalence problems are decidable. These results hold for other machines, e.g., when the worktapes are pushdown stacks (where on every step, each pushdown can only pop the top of the stack or replace the top of the stack by at most two symbols) or when stacks are counters (where on every step, a counter can be incremented by 1, decremented by 1, or remain unchanged, and can be tested for zero). Our results are the best possible in the sense that not parameterizing one of (or, in the case of counter machines, allowing the counters to increment by arbitrary integers that may change from machines to machines) makes the universe problem undecidable. We also give a simple characterization of the languages defined by . Finally, we investigate the applicability of our techniques to machines with multiple input heads or multiple input tapes. [Copyright &y& Elsevier]

Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane triangulation. In comparison with previous floor-planning algorithms in the literature, our solution is not only simpler in the algorithm itself, but also produces floor-plans which require fewer module types. An equally important aspect of our new algorithm lies in its ability to fit the floor-plan area in a rectangle of size (n−1)×⌊(2n+1)/3⌋. Lower bounds on the worst-case area for floor-planning any plane triangulation are also provided in the paper. [Copyright &y& Elsevier]

Assume that there are players and an eavesdropper Eve, where several pairs of players have shared secret keys beforehand. We regard each player as a vertex of a graph and regard each pair of players sharing a key as an edge. Consider the case where Eve knows some of the keys according to a certain probability distribution. In this paper, applying the technique of st-numbering, we propose a protocol which allows any two designated players to agree on a secret key through such a "partially leaked key exchange graph." Our protocol is optimal in the sense that Eve's knowledge about the secret key agreed on by the two players is as small as possible. [ABSTRACT FROM AUTHOR]

In this paper, we study the bounded space variation, especially one-space bounded, of two-dimensional bin packing. A sequence of rectangular items arrive over time, and the following item arrives after the packing of the previous one. The height and width of each item are no more than 1, we need to pack these items into unit square bins of size 1 × 1 where rotation of 90° is allowed and our objective is to minimize the number of used bins. Once an item is packed into a square bin, the position of this item is fixed and it cannot be shifted within this bin. At any time, there is at most one active bin; the current unpacked item can be only packed into the active bin and the inactive bins (closed at some previous time) cannot be used for any future items. We first propose an online algorithm with a constant competitive ratio 12, then improve the competitive ratio to 8.84 by the some complicated analysis. Our results significantly improve the previous best known O((log log m)2)-competitive algorithm [10], where m is the width of the square bin and the size of each item is a × b, where a, b are integers no more than m. Furthermore, the lower bound for the competitive ratio is also improved to 2.5. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The k-tour cover problem is known to be $\mathcal{N}\mathcal{P}$-hard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomial-time approximation scheme (PTAS) for small values of k, k = Ø(log n/log log n). In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k ≤ 2logδ n, where δ = δ(ε). The main technical result proved in the paper is a novel reduction of the k-tour cover problem with a set of n points to a small set of instances of the problem, each with Ø((k/ε)Ø(1)) points. [ABSTRACT FROM AUTHOR]

In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. It has been known that the perfect matching problem for the classes of hypergraphs H with minimum ((k - 1)-wise) vertex degreeδ(H) at least c|V(H)| is NP-complete for $c < \frac{1}{k}$ and trivial for c ≥ ½, leaving the status of the problem with c in the interval $[\frac{1}{k}, \frac{1}{2})$ widely open. In this paper we show, somehow surprisingly, that ½ is not the threshold for tractability of the perfect matching problem, and prove the existence of an ε > 0 such that the perfect matching problem for the class of hypergraphs H with δ(H) ≥ (½ - ε)|V(H)| is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest. [ABSTRACT FROM AUTHOR]

We study the problem of finding all maximal approximate gapped palindromes in a string. More specifically, given a string S of length n, a parameter q ≥ 0 and a threshold k > 0, the problem is to identify all substrings in S of the form uvw such that (1) the Levenshtein distance between ur and w is at most k, where ur is the reverse of u and (2) v is a string of length q. The best previous work requires O(k2n) time. In this paper, we propose an O(kn)-time algorithm for this problem by utilizing an incremental string comparison technique. It turns out that the core technique actually solves a more general incremental string comparison problem that allows the insertion, deletion, and substitution of multiple symbols. [ABSTRACT FROM AUTHOR]

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. In the second part of the paper we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup S of integral square matrices whether or not the identity matrix belongs to S?". We show that the problem is undecidable starting from dimension four even when the number of matrices in the generator is 48. From this fact, we can immediately derive that the fundamental problem of whether a finite set of matrices generates a group is also undecidable. We also answer several questions for matrices over different number fields. Apart from the application to matrix problems, we believe that the Identity Correspondence Problem will also be useful in identifying new areas of undecidable problems in abstract algebra, computational questions in logic and combinatorics on words. [ABSTRACT FROM AUTHOR]

In this paper we study three popular on-line disk scheduling algorithms, FCFS, SSTF, and LOOK, using competitive analysis. Our results show that, in a competitive sense, the performance of LOOK is better than those of SSTF and FCFS. As a by-product, our analysis also reveals quantitatively the role played by the size of the window, which in our model is a waiting buffer that holds a fixed number of requests waiting to be serviced next. The window, in some sense, offers the lookahead ability which is mentioned in several on-line problems. [ABSTRACT FROM AUTHOR]