共查询到20条相似文献,搜索用时 31 毫秒
1.
M. Pellegrini 《Algorithmica》1993,9(5):471-494
We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR 3 into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems:
- Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles.
- Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term.
- Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term.
- Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra.
- Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.
2.
Stable semantics for disjunctive programs 总被引:1,自引:0,他引:1
Teodor C. Przymusinski 《New Generation Computing》1991,9(3-4):401-424
We introduce the stable model semantics fordisjunctive logic programs and deductive databases, which generalizes the stable model semantics, defined earlier for normal (i.e., non-disjunctive) programs. Depending on whether only total (2-valued) or all partial (3-valued) models are used we obtain thedisjunctive stable semantics or thepartial disjunctive stable semantics, respectively. The proposed semantics are shown to have the following properties: ? For normal programs, the disjunctive (respectively, partial disjunctive) stable semantics coincides with thestable (respectively,partial stable) semantics. ? For normal programs, the partial disjunctive stable semantics also coincides with thewell-founded semantics. ? For locally stratified disjunctive programs both (total and partial) disjunctive stable semantics coincide with theperfect model semantics. ? The partial disjunctive stable semantics can be generalized to the class ofall disjunctive logic programs. ? Both (total and partial) disjunctive stable semantics can be naturally extended to a broader class of disjunctive programs that permit the use ofclassical negation. ? After translation of the programP into a suitable autoepistemic theory \( \hat P \) the disjunctive (respectively, partial disjunctive) stable semantics ofP coincides with the autoepistemic (respectively, 3-valued autoepistemic) semantics of \( \hat P \) . 相似文献
3.
Given a rewriting system G (its alphabet, the set of productions and the axiom) one can define the language of G by
- taking out of all strings generated by G only those which are over a distinguished subalphabet of G, or
- translating the set of all strings generated by G by a fixed homomorphism.
4.
We report progress on the NL versus UL problem. We show that counting the number of s-t paths in graphs where the number of s-v paths for any v is bounded by a polynomial can be done in FUL: the unambiguous log-space function class. Several new upper bounds follow from this including ${{{ReachFewL} \subseteq {UL}}}$ and ${{{LFew} \subseteq {UL}^{FewL}}}$ We investigate the complexity of min-uniqueness—a central notion in studying the NL versus UL problem. In this regard we revisit the class OptL[log n] and introduce UOptL[log n], an unambiguous version of OptL[log n]. We investigate the relation between UOptL[log n] and other existing complexity classes. We consider the unambiguous hierarchies over UL and UOptL[log n]. We show that the hierarchy over UOptL[log n] collapses. This implies that ${{{ULH} \subseteq {L}^{{promiseUL}}}}$ thus collapsing the UL hierarchy. We show that the reachability problem over graphs embedded on 3 pages is complete for NL. This contrasts with the reachability problem over graphs embedded on 2 pages, which is log-space equivalent to the reachability problem in planar graphs and hence is in UL. 相似文献
5.
María Victoria Cengarle Luis Mandel Martin Wirsing Heiner Brand Klaus Däßler Thekla Schneider 《Higher-Order and Symbolic Computation》1992,4(4):319-369
A DIN Kernel LISP Draft (DKLisp) has been developed by DIN as Reaction to Action D1 (N79), short term goal, of ISO WG16. It defines a subset language, as compatible as possible with the ANSICommon-Lisp draft, but also with theEuLisp draft. It combines the most important LISP main stream features in a single, compact, but nevertheless complete language definition, which thereby could be well suited as basis for a short term InternationalLisp Standard. Besides the functional and knowledge processing features, the expressive power of the language is well comparable with contemporary procedural languages, as e.g. C++ (of course without libraries). Important features ofDKLisp are: to be a “Lisp-1,” but allowing an easy “Lisp-2” transformation; to be a simple, powerful and standardized educationalLisp; to omit all features, which are unclean or in heavy discussion; DKLisp programs run nearly unchanged inCommon-Lisp; DKLisp contains a simple object and package system; DKLisp contains those data classes and control structures also common to most modernLisp and non-Lisp languages; DKLisp offers a simple stream I/O; DKLisp contains a clean unified hierarchical class/type system; DKLisp contains the typical “Lisp-features” in an orthogonal way; DKLisp allows and encourages really small but powerful implementations; DKLisp comes in levels, so allowing ANSICommon-Lisp to be an extension ofDKLisp level-1. The present is the second version of the proposal, namely version 1.2, with slight differences with respect to the one sent to ISO. Sources of such changes were the remarks generously sent by many readers of the previous attempt. 相似文献
6.
7.
J. M. Martínez 《Computing》1987,39(4):307-325
We introduce a new method for solving Nonlinear Least Squares problems when the Jacobian matrix of the system is large and sparse. The main features of the new method are the following:
- The Gauss-Newton equation is “partially” solved at each iteration using a preconditioned Conjugate Gradient algorithm.
- The new point is obtained using a two-dimensional trust region scheme, similar to the one introduced by Bulteau and Vial.
8.
A data encoding is a formal model of how a logical data structure is mapped into or represented in a physical storage structure. Both structures are complete trees in this paper, and we encode the logical or guest tree in the leaves of the physical or host tree giving a restricted class of encodings called entreeings. The cost of an entreeing is the total amount that the edges of the guest tree are stretched or dilated when they are replaced by shortest paths in the host tree. We are particularly interested in the asymptotic average cost of families of similar entreeings. Our investigation is a continuation of the study initiated by Rosenberg et al. In particular, the paper contains the following results.
- We refute a conjecture of Rosenberg et al. that a particular family of entreeings of binary guests into binary hosts is optimal.
- We provide an efficient family of entreeings fork-ary guests intok-ary hosts, fork≧2.
- We provide an efficient family of entreeings ofk-ary guests into binary hosts, fork≧3.
- We provide a new simple lower-bound technique that can be applied to the entreeings in part 2 to prove that they are very close to optimal. Moreover, it can be adapted for the entreeings of part 3, in which case we are able to show near optimality whenk is sufficiently large.
9.
Dr. S. -S. Lin 《Computing》1994,52(1):1-15
We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a comptuation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through it several times. We can think it as a “hardware subroutine”. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study:
- The sum ofn bits can be computed in O(1) times on a PARBS with O(n 1+?) processors for any fixed ?>0.
- The weights of each simple path of ann*n image can be computed in O(1) time on a 3-D PARBS with O(n 2+?) processors for any fixed ?>0.
- Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n 2+?) processors for any fixed ?>0 withp copies of the image pretiled.
- Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n 3) processors.
10.
We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). LetP be a trapezoided rectilinear simple polygon withn vertices. InO(logn) time usingO(n/logn) processors we can optimally compute:
- Minimum réctilinear link paths, or shortest paths in theL 1 metric from any point inP to all vertices ofP.
- Minimum rectilinear link paths from any segment insideP to all vertices ofP.
- The rectilinear window (histogram) partition ofP.
- Both covering radii and vertex intervals for any diagonal ofP.
- A data structure to support rectilinear link-distance queries between any two points inP (queries can be answered optimally inO(logn) time by uniprocessor).
11.
Tom Conlon 《Artificial Intelligence Review》1992,6(3):285-324
If you are familiar with Prolog but not with Parlog then this tutorial is aimed at you. In what follows I attempt to: ? explain the basics of Parlog ? demonstrate that Parlog programs can be powerful and elegant ? discuss the relationship of Parlog to Prolog, and ? identify some resources which will take you further. These are what I call ‘four steps to Parlog’. 相似文献
12.
Christian Choffrut Flavio D’Alessandro Stefano Varricchio 《Theory of Computing Systems》2010,46(2):351-369
In this paper, for a finitely generated monoid M, we tackle the following three questions:
- Is it possible to give a characterization of rational subsets of M which have polynomial growth?
- What is the structure of the counting function of rational sets which have polynomial growth?
- Is it true that every rational subset of M has either exponential growth or it has polynomial growth? Can one decide for a given rational set which of the two options holds?
13.
In this paper we investigate the expected complexityE(C) of distributive (“bucket”) sorting algorithms on a sampleX 1, ...,X n drawn from a densityf onR 1. Assuming constant time bucket membership determination and assuming the use of an average timeg(n) algorithm for subsequent sorting within each bucket (whereg is convex,g(n)/n↑∞,g(n)/n 2 is nonincreasing andg is independent off), the following is shown:
- Iff has compact support, then ∫g(f(x))dx<∞ if and only ifE(C)=0(n).
- Iff does not have compact support, then \(E(C)/n\xrightarrow{n}\infty \) .
14.
Scale-space behaviour of local extrema and blobs 总被引:4,自引:0,他引:4
Tony Lindeberg 《Journal of Mathematical Imaging and Vision》1992,1(1):65-99
15.
Brady Garvin Derrick Stolee Raghunath Tewari N. V. Vinodchandran 《Computational Complexity》2014,23(1):85-98
We show that two complexity classes introduced about two decades ago are unconditionally equal. ReachUL is the class of problems decided by nondeterministic log-space machines which on every input have at most one computation path from the start configuration to any other configuration. ReachFewL, a natural generalization of ReachUL, is the class of problems decided by nondeterministic log-space machines which on every input have at most polynomially many computation paths from the start configuration to any other configuration. We show that ReachFewL = ReachUL. 相似文献
16.
Efficiently extendible mappings for balanced data distribution 总被引:2,自引:0,他引:2
In data storage applications, a large collection of consecutively numbered data “buckets” are often mapped to a relatively small collection of consecutively numbered storage “bins.” For example, in parallel database applications, buckets correspond to hash buckets of data and bins correspond to database nodes. In disk array applications, buckets correspond to logical tracks and bins correspond to physical disks in an array. Measures of the “goodness” of a mapping method include:
- Thetime (number of operations) needed to compute the mapping.
- Thestorage needed to store a representation of the mapping.
- Thebalance of the mapping, i.e., the extent to which all bins receive the same number of buckets.
- The cost ofrelocation, that is, the number of buckets that must be relocated to a new bin if a new mapping is needed due to an expansion of the number of bins or the number of buckets.
17.
Frank Dehne 《The Visual computer》1988,3(6):356-370
In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms: - AnO( \(\sqrt N\) time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes. -O( \(\sqrt N\) ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond. - AnO( \(\sqrt N\) ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( \(\sqrt {MN}\) ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction. All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors. 相似文献
18.
Anatomic snapshot memory object in shared memory systems enables a set of processes, calledscanners, to obtain a consistent picture of the shared memory while other processes, calledupdaters, keep updating memory locations concurrently. In this paper we present two conversion methods of snapshot implementations. Using the first conversion method we obtain a new snapshot implementation in which the scan operation has linear time complexity and the time complexity of the update operation becomes the sum of the time complexities of the original implementation. Applying the second conversion method yields similar results, where in this case the time complexity of the update protocol becomes linear. Although our conversion methods use unbounded space, their space complexity can be bounded using known techniques. One of the most intriguing open problems in distributed wait-free computing is the existence of a linear-time implementation of this object. Using our conversion methods and known constructions we obtain the following results: ?Consider a system ofn processes, each an updater and a scanner. We present an implementation in which the time complexity of either the update or the scan operation is linear, while the time complexity of the second operation isO(n logn). ?We present an implementation with linear time complexity when the number of either updaters or scanners isO(n/logn), wheren is the total number of processes. ?We present an implementation with amortized linear time complexity when one of the protocols (either upate or scan) is executed significantly more often than the other protocol. 相似文献
19.
We give unified and simplified algorithms and proofs for three results on channel routing in knock-knee mode. LetP be a channel routing problem with densityd max.
- [Rivest/Baratz/Miller, Preparata/Lipski]. If all nets inP are two-terminal nets thend max tracks suffice.
- [Preparata/Sarrafzadeh]. If all nets inP are two- or three-terminal nets then [3d max/2] tracks suffice.
- [Sarrafzadeh/Preparata]. 2d max-1 tracks always suffice.
20.
Foued Ameur Paul Fischer Klaus -U. Höffgen Friedhelm Meyer auf der Heide 《Acta Informatica》1996,33(5):621-630
A pac-learning algorithm isd-space bounded, if it stores at mostd examples from the sample at any time. We characterize thed-space learnable concept classes. For this purpose we introduce the compression parameter of a concept classb and design our Trial and Error Learning Algorithm. We show: b isd-space learnable if and only if the compression parameter ofb is at mostd. This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes: - all intersection closed concept classes with finite VC-dimension. - convexn-gons in ?2. - halfspaces in ?n. - unions of triangles in ?2. We further relate the compression parameter to the VC-dimension, and discuss variants of this parameter. 相似文献