waashk/dblp huggingface dataset:
computing farthest neighbors on a convex polytope. let n be a set of n points in convex position in r3. the farthest point voronoi diagram of n partitions r3 into n convex cells. we consider the intersection g(n) of the diagram with the boundary of the convex hull of n. we give an algorithm that computes an implicit representation of g(n) in expected o(n log2 n) time. more precisely, we compute the combinatorial structure of g(n), the coordinates of its vertices, and the equation of the plane defining each edge of g(n). the algorithm allows us to solve the all-pairs farthest neighbor problem for n in expected time o(n log2 n), and to perform farthest-neighbor queries on n in o(log2 n) time with high probability.
additive sparse spanners for graphs with bounded length of largest induced cycle. in this paper, we show that every chordal graph with n vertices and m edges admits an additive 4-spanner with at most 2n - 2 edges and an additive 3-spanner with at most o(n log n) edges. this significantly improves results of peleg and schäffer from [graph spanners, j. graph theory 13 (1989) 99-116]. our spanners are additive and easier to construct. an additive 4-spanner can be constructed in linear time while an additive 3-spanner is constructable in o(m log n) time. furthermore, our method can be extended to graphs with largest induced cycles of length k. any such graph admits an additive (k + 1)-spanner with at most 2n - 2 edges which is constructable in o(nk + m) time.
interval routing in some planar networks. in this article, we design optimal or near optimal interval routing schemes (irs, for short) with small compactness for several classes of plane quadrangulations and triangulations (by optimality or near optimality we mean that messages are routed via shortest or almost shortest paths). we show that the subgraphs of the rectilinear grid bounded by simple circuits allow optimal irs with at most two circular intervals per edge (2-irs). we extend this result to all plane quadrangulations in which all inner vertices have degrees ≥ 4. namely, we establish that every such graph has an optimal irs with at most seven linear intervals per edge (7-lirs). this leads to a 7-lirs with the stretch factor 2 for all plane triangulations in which all inner vertices have degrees ≥ 6. all routing schemes can be implemented in linear time.
upper semi-lattice of binary strings with the relation "x is simple conditional to y". in this paper we construct a structure r that is a "finite version" of the semi-lattice of turing degrees. its elements are strings (technically, sequences of strings) and xy means thatk(x|y)=(conditional kolmogorov complexity of x relative to y) is small. we construct two elements in r that do not have greatest lower bound. we give a series of examples that show how natural algebraic constructions give two elements that have lower bound 0 (minimal element) but significant mutual information. (a first example of that kind was constructed by g&aacute;cs-k&ouml;rner (problems control inform. theory 2 (1973) 149) using a completely different technique.) we define a notion of "complexity profile" of the pair of elements of r and give (exact) upper and lower bounds for it in a particular case.
associative language descriptions. the new associative language description (ald) model, a combination of locally testable and constituent structure ideas, is proposed, arguing that in practice it equals context-free (cf) grammars in explanatory adequacy, yet it provides a simple description and it excludes mathematical sets based on counting properties, which are rarely (if ever) used in compiler construction or in computational linguistics. the ald model has been recently proposed as an approach consistent with current views on brain organization. ald is a "pure", i.e., nonterminal-free definition. the strict inclusion of ald languages in cf languages is proved, based on a lemma which strengthens the pumping lemma for cf languages. basic nonclosure and undecidability properties are considered and compared with those of cf languages. it is shown that the hardest context-free language is in ald, that there exists a hierarchy of ald languages and that each ald tree language enjoys the noncounting property of parenthesized cf languages. typical technical languages (pascal, html) can be rather conveniently described by ald rules
picture languages: tiling systems versus tile rewriting grammars. two formal models of pictures, i.e., two dimensional (2d) languages are compared: tiling systems and tile rewriting grammars, which resp. extend to 2d the regular and context-free languages. two results extending classical language properties into 2d are proved. first, non-recursive tile writing grammars (trg) coincide with tiling systems (ts). second, non-self-embedding trg are suitably defined as corner grammars, showing that they generate ts languages. the proofs exploit newly introduced language substitutions, also nested and iterated.
load-balanced parallel banded-system solvers. solving banded systems is important in the applications of science and engineering. this paper presents a load-balancing strategy for solving banded systems in parallel when the number of processors used is small. an optimization-based load-balancing analysis is given to determine how many loads should be assigned to each processor in order to minimize the time requirement. some experimentations are carried out on the ncube 2e multiprocessor to demonstrate the speedup advantage of the proposed load-balancing strategy. the speedup improvement ratio ranges from 47% to 66% (from 12% to 24%) when using 4 (8) processors.
about local configurations in arithmetic planes. in vittone and chassery (proc. of dgci'97, vol. 1347 of lecture notes in computer sciences, 1997, pp. 87-98) j.-m. chassery and j. vittone studied local configurations of (m,n)-cubes in naive planes in function of the parameters of these naive planes. more precisely, they enumerated the bicubes and the tricubes that appear in a naive hyperplane of parameters (a,b,c). a symmetry about the line c=a+b appears clearly in this enumeration. the aim of this paper is to prove that the configurations of (nn)-cubes in the plane of parameters (a,b,c) are in one-to-one relation with those in the plane of parameters (c-b, c-a,c). if we restrict the parameters to the planes such that a+bc, we note a second symmetry about the line c=2b; we also prove this symmetry. we generalize a theorem established by rveilles and grard (grard, proc. of dgci'99, vol. 1568 of lecture notes in computer sciences, 1999, pp. 65-75, reveilles, vision geometry 4, vol. 2573 of spie 95, san diego, 1995) and these symmetries to the local configurations of planes of given thickness.
relating defeasible and normal logic programming through transformation properties. this paper relates the defeasible logic programming (delp) framework and its semantics semdelp to classical logic programming frameworks. in delp, we distinguish between two different sorts of rules: strict and defeasible rules. negative literals (∼a) in these rules are considered to represent classical negation. in contrast to this, in normal logic programming (nlp), there is only one kind of rules, but the meaning of negative literals (not a) is different: they represent a kind of negation as failure, and thereby introduce defeasibility. various semantics have been defined for nlp, notably the well-founded semantics (wfs) (van gelder et al., proceedings of the seventh symposium on principles of database systems, 1988, pp. 221-230; j. acm 38 (3) (1991) 620) and the stable semantics stable (gelfond and lifschitz, fifth conference on logic programming, mit press, cambridge, ma, 1988, pp. 1070-1080; proceedings of the seventh international conference on logical programming, jerusalem, mit press, cambridge, ma, 1991, pp. 579-597).in this paper we consider the transformation properties for nlp introduced by brass and dix (j. logic programming 38(3) (1999) 167) and suitably adjusted for the delp framework. we show which transformation properties are satisfied, thereby identifying aspects in which nlp and delp differ. we contend that the transformation rules presented in this paper can help to gain a better understanding of the relationship of delp semantics with respect to more traditional logic programming approaches. as a byproduct, we obtain the result that delp is a proper extension of nlp.
switched pioa: parallel composition via distributed scheduling. this paper presents the framework of switched probabilistic input/output automata (or switched pioa), augmenting the original pioa framework with an explicit control exchange mechanism. using this mechanism, we model a network of processes passing a single token among them, so that the location of this token determines which process is scheduled to make the next move. this token structure therefore implements a distributed scheduling scheme: scheduling decisions are always made by the (unique) active component.distributed scheduling allows us to draw a clear line between local and global nondeterministic choices. we then require that local nondeterministic choices are resolved using strictly local information. this eliminates unrealistic schedules that arise under the more common centralized scheduling scheme. as a result, we are able to prove that our trace-style semantics is compositional.
locating factors of the infinite fibonacci word. let τ = (√5 - 1)/2. let a, b be two distinct letters. the infinite fibonacci word is the infinite word g = babbababbabbababbababbabba... whose nth letter is a (resp., b) if [(n + 1)τ] - [nτ] = 0 (resp., 1). for a factor w of g, the location of w is the set of all positions in g at which w occurs. only the locations of the following factors of g are already known: squares, singular words and those factors of g whose lengths are fibonacci numbers. the purpose of this paper is to determine the locations of all factors of g. our results contain all the known ones as consequences. moreover, using our results, we are able to identify any factor of g whenever its starting position and length are given; also we are able to tell whether two suffixes of g have a common prefix of a certain length.
an np decision procedure for protocol insecurity with xor. we provide a method for deciding the insecurity of cryptographic protocols in the presence of the standard dolev-yao intruder (with a finite number of sessions) extended with so-called oracle rules, i.e., deduction rules that satisfy certain conditions. as an instance of this general framework, we obtain that protocol insecurity is in np for an intruder that can exploit the properties of the exclusive or (xor) operator. this operator is frequently used in cryptographic protocols but cannot be handled in most protocol models. an immediate consequence of our proof is that checking whether a message can be derived by an intruder (using xor) is in ptime. we also apply our framework to an intruder that exploits properties of certain encryption modes such as cipher block chaining (cbc).
a certified, corecursive implementation of exact real numbers. we implement exact real numbers in the logical framework coq using streams, i.e., infinite sequences, of digits, and characterize constructive real numbers through a minimal axiomatization. we prove that our construction inhabits the axiomatization, working formally with coinductive types and corecursive proofs. thus we obtain reliable, corecursive algorithms for computing on real numbers.
approximate and dynamic rank aggregation. rank aggregation, originally an important issue in social choice theory, has become more and more important in information retrieval applications over the internet, such as meta-search, recommendation system, etc. in this work, we consider an aggregation function using a weighted version of the normalized kendall-τ distance. we propose a polynomial time approximation scheme, as well as a practical heuristic algorithm with the approximation ratio two for the np-hard problem. in addition, we discuss issues and models for the dynamic rank aggregation problem.
least adaptive optimal search with unreliable tests. we consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes-no questions, when up to a finite number e of the answers may be erroneous. in case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by ulam and r&&eacute;nyi and is strictly related to berlekamp's theory of error correcting communication with noiseless feedback. conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. let qe(m) be the smallest integer q satisfying berlekamp's bound i=0e()2qm. then at least qe(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. in the fully adaptive case, optimal searching strategies using exactly qe(m) questions always exist up to finitely many exceptional m's. at the opposite non-adaptive case, searching strategies with exactly qe(m) questions or equivalently, e-error correcting codes with 2m codewords of length qe(m)---are rather the exception, already for e=2, and are generally not known to exist for e>2. in this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of qe(m)m non-adaptive questions. these strategies are automatically optimal. since even in the fully adaptive case, qe(m)1 questions do not suffice to find the unknown number, and qe(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e, fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.
improved competitive algorithms for online scheduling with partial job values. this paper considers an online scheduling problem arising from quality-of-service (qos) applications. we are required to schedule a set of jobs, each with release time, deadline, processing time and weight. the objective is to maximize the total value obtained for scheduling the jobs. unlike the traditional model of this scheduling problem, in our model unfinished jobs also get partial values proportional to their amounts processed.no non-timesharing algorithm for this problem with competitive ratio better than 2 is known. we give a new non-timesharing algorithm gap that improves this ratio for bounded values of m, where m can be the number of concurrent jobs or the number of weight classes. the competitive ratio is improved from 2 to 1.618 (golden ratio) which is optimal for m = 2, and when applied to cases with m > 2 it still gives a competitive ratio better than 2, e.g. 1.755 when m = 3. we also give a new study of the problem in the multiprocessor setting, giving an upper bound of 2 and a lower bound of 1.25 for the competitiveness. finally, we consider resource augmentation and show that o(log α) speedup or extra processors is sufficient to achieve optimality, where α is the importance ratio. we also give a tradeoff result, showing that in fact a small amount of extra resources is sufficient for achieving close-to-optimal competitiveness.
static and dynamic low-congested interval routing schemes. interval routing schemes (irs) have been extensively investigated in the past years with special emphasis on shortest paths. besides their theoretical interest, irs have practical applications, as they have been implemented with wormhole routing in the last generation of inmos transputer router chips. in this paper we consider irs that are optimal with respect to the congestion of the induced path system. in fact, wormhole routing is strongly influenced by the maximum number of paths that share a physical link and from low to moderate congestion it outperforms the packet switching technique. we provide a general framework able to deal with the various congestion issues in irs. in fact, we will distinguish between static cases, in which the source-destination configurations are fixed, and dynamic cases, where they vary over time. all these situations can be handled in a unified setting, thanks to the notion of competitiveness introduced in this paper. we first give some general results not related to specific traffic demands. then, in the one-to-all communication pattern, we show that constructing competitive irs for a given network is an intractable problem, both for the static and the dynamic case, that is when the root vertex is fixed and when it can change along the time, respectively. finally, both for one-to-all and all-to-all communication patterns, we provide nicely competitive k-irs for relevant topologies. networks considered are chains, trees, rings, chordal rings and multi-dimensional grids and tori. we consider both the directed congestion case, in which there are pairwise opposite unidirectional links connecting two neighbor processors, and the undirected congestion case, in which two neighbors are connected by a single bi-directional link.
improved approximation of the minimum cover time. feige and rabinovich, in [feige and rabinovich, rand. struct. algorithms 23(1) (2003) 1-22], gave a deterministic o(log4n) approximation for the time it takes a random walk to cover a given graph starting at a given vertex. this approximation algorithm was shown to work for arbitrary reversible markov chains. we build on the results of [feige and rabinovich, rand. struct. algorithms 23(1) (2003) 1-22], and show that the original algorithm gives a o(log2n) approximation as it is, and that it can be modified to give a o(log n(log log n)2) approximation. moreover, we show that given any c(n)-approximation algorithm for the maximum cover time (maximized over all initial vertices) of a reversible markov chain, we can give a corresponding algorithm for the general cover time (of a random walk or reversible markov chain) with approximation ratio o(c(n) log n).
complexity of approximating bounded variants of optimization problems. we study low degree graph problems such as maximum independent set and minimum vertex cover. the goal is to improve approximation lower bounds for them and for a number of related problems like max-b-set packing, min-b-set cover, and max-b-dimensional matching, b≥3. we prove, for example, that it is np-hard to achieve an approximation factor of 95/94 for max-3-dm, and a factor of 48/47 for max-4-dm. in both cases the hardness result applies even to instances with exactly two occurrences of each element.
partial digest is hard to solve for erroneous input data. the partial digest problem asks for the coordinates of m points on a line such that the pairwise distances of the points form a given multiset of (m 2) distances. partial digest is a well-studied problem with important applications in physical mapping of dna molecules. its computational complexity status is open. input data for partial digest from real-life experiments are always prone to error, which suggests to study variations of partial digest that take this fact into account. in this paper, we study the computational complexity of partial digest variants that model three different error types that can occur in the data: additional distances, missing distances, and erroneous fragment lengths. we show that these variations are np-hard, hard to approximate, and strongly np-hard, respectively.
three-player partizan games. conway's theory of partizan games is both a theory of games and a theory of numbers. we present here an extension such a theory to classify three-player partizan games. we apply this extension to solve a restricted version of three-player hackenbush.
molecular interaction. we introduce and study abstract structures which are suitable for expressing molecular interaction. the abstract structures are able to manage shared resources and to describe the use of shared resources. we show that these structures can provide an interpretation of the π-calculus, a known calculus of communicating concurrent systems. we briefly describe dna methylation by using the π-calculus. molecular interactions during dna methylation imply changes of conformation and other modifications; these changes can be modelled by substitutions. formally, we use some notions and results of the concurrency theory, particularly related to the π-calculus and multiset semantics.
a coalgebraic equational approach to specifying observational structures. a coalgebraic, equational approach to the specification of observational structures allowing for a choice in the result type of observations is presented. observers whose result type is structured as a coproduct of basic types are considered, and notions of covariable, coterm and coequation, dual to the algebraic notions of variable, term and equation are used to specify the associated structures. a sound and complete deduction calculus for reasoning about observational structures is then formulated. finally, the approach is extended in order to account for the availability of a fixed data universe in the specification of such structures.
a compositional approach to defining logics for coalgebras. we present a compositional approach to defining expressive logics for coalgebras of endofunctors on set. this approach uses a notion of language constructor and an associated notion of semantics to capture one inductive step in the definition of a language for coalgebras and of its semantics. we show that suitable choices for the language constructors and for their associated semantics yield logics which are both adequate and expressive w.r.t, behavioural equivalence. moreover, we show that type-building operations give rise to corresponding operations both on language constructors and on their associated semantics, thus allowing the derivation of expressive logics for increasingly complex coalgebraic types. our framework subsumes several existing approaches to defining logics for coalgebras, and at the same time allows the derivation of new logics, with logics for probabilistic systems being the prime example.
collage of two-dimensional words. we consider a new operation on one-dimensional (resp. two-dimensional) word languages, obtained by piling up, one on top of the other, words of a given recognizable language (resp. two-dimensional recognizable language) on a previously empty one-dimensional (resp. two-dimensional) array. the resulting language is the set of words "seen from above": a position in the array is labeled by the topmost letter. we show that in the one-dimensional case, the language is always recognizable. this is no longer true in the two-dimensional case which is shown by a counter-example, and we investigate in which particular cases the result may still hold.