Search results for " Applications"
showing 10 items of 4541 documents
Exact, efficient, and complete arrangement computation for cubic curves
2006
AbstractThe Bentley–Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and Bézier curves.The algorithm is complete in that it handles all possible degeneracies such as tangential intersections and singularities. It is exact in t…
Analysis of Optimal High Resolution and Fixed Rate Scalar Quantization
2009
In 2001, Hui and Neuhoff proposed a uniform quantizer with overload for the quantization of scalar signals and derived the asymptotically optimal size of the quantization bins in the high-bitrate limit. The purpose of the present paper is to prove a quantitatively more precise version of this result which, at the same time, is valid for a more general, quite natural class of probability distributions that requires only little regularity and includes, for instance, positive Lipschitz-continuous functions of unit integral.
On the listing and random generation of hybrid binary trees
1994
We consider in this paper binary trees whose internal nodes are either associative or non-associative. Hybrid binary trees are equivalence classes with respect to the associative property. We count, list and generate randomly hybrid binary trees using Fibonacci numbers.
Root-restricted Kleenean rotations
2010
We generalize the Kleene theorem to the case where nonassociative products are used. For this purpose, we apply rotations restricted to the root of binary trees.
On the regularity of circular splicing languages : A survey and new developments
2009
Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we focus on the relationship between regular circular languages and languages generated by finite circular splicing systems. We survey the known results towards a characterization of the intersection between these two classes and provide new contributions on the open problem of finding this characterization. First, we exhibit a non-regular circular language generated by a circular simple system thus disproving a known result in this area. Then we give new results related to a restrictive class of circular splicing systems…
Superiority Of One-Way And Realtime Quantum Machines
2012
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime push…
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
2008
We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumaki on the cha- racterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators, we prove that if H and K are two finitely generated submonoids generated by prefix sets such that the product automaton associated to H ∩ K has a given special property then �(H ∩ K) ≤ �(H)�(K…
Extensions and intentions in the rough set theory
1998
Abstract The approach to rough set theory proposed in this paper is based on the mutual correspondence of the concepts of extension and intension. It is different from the well-known approaches in the literature in that the upper approximations and the lower approximations of ‘unknown’ sets are considered as certain families of ‘known’ sets. This approach makes it possible to formulate necessary and sufficient conditions for the existence of operations on rough sets, which are analogous to classical operations on sets. The basic results presented in this paper, based on certain ideas of the second author, were formulated by the first author in his doctoral dissertation prepared under the su…
On a pair of fuzzy $\varphi$-contractive mappings
2010
We establish common fixed point theorems for fuzzy mappings under a $\varphi$-contraction condition on a metric space with the d_$\infty$-metric (induced by the Hausdorff metric) on the family of fuzzy sets. The study of fixed points of fuzzy set-valued mappings related to the d_$\infty$-metric is useful in geometric problems arising in high energy physics. Our results generalize some recent results.