waashk/dblp huggingface dataset:
competitive analysis of incentive compatible on-line auctions. this paper studies auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. such settings occur in computerized auctions of computational resources as well as in other settings. we call such auctions, on-line auctions.we first characterize exactly on-line auctions that are incentive compatible, i.e. where rational bidders are always motivated to bid their true valuation. we then embark on a competitive worst-case analysis of incentive compatible on-line auctions. we obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. this auction has an optimal competitive ratio, both in terms of seller's revenue and in terms of the total social efficiency obtained.
idempotent analysis and continuous semilattices. in this survey article we give a brief overview of various aspects of the recently emerging field of idempotent analysis and suggest potential connections with domain theory.
riemann and edalat integration on domains. the main result of this paper is that the domain-theoretic approach to the generalized riemann integral first introduced by edalat extends to a large class of spaces that can be realized as the set of maximal points of domains.the approach is based on the theory of a riemann-stieltjes type integral on a topological space with respect to a finitely additive measure. we develop the theory of this integral for a bounded function f defined on the maximal points of a continuous domain and show that it gives an alternate approach to the edalat integral.
posets having continuous intervals. in this paper we consider posets in which each order interval [a, b] is a continuous poset or continuous domain. after developing some basic theory for such posets, we derive our major result: if x is a core compact space and l is a poset equipped with the scott topology (assumed to satisfy a mild extra condition) for which each interval is a continuous sup-semilattice, then the function space of continuous locally bounded functions from x into l has intervals that are continuous sup-semilattices. this substantially generalizes known results for continuous domains.
left and right adjoint operations on spaces and data types. formal theories of higher types need to be augmented to permit treatment of some additional right adjoints which arise in mathematical practice. the concomitant mathematical scrutiny of supposedly well-established left adjoints resurrects a "critique of foundations" which may not be irrelevant for practice. categorical methods based on mathematical experience with the diversity of toposes allow us to address such problems without getting entangled in sterile ontological debates.
close to optimal decentralized routing in long-range contact networks. in order to explain the ability of individuals to find short paths to route messages to an unknown destination, based only on their own local view of a social network (the small world phenomenon), kleinberg [the small-world phenomenon: an algorithmic perspective, proc. 32nd acm symp. on theory of computing, 2000, pp. 163-170] proposed a network model based on a d-dimensional lattice of size n augmented with k long-range directed links per node. individuals behavior is modeled by a greedy algorithm that, given a source and destination, forwards a message to the neighbor of the current holder, which is the closest to the destination. this algorithm computes paths of expected length θ(log2 n/k) between any pair of nodes. other topologies have been proposed later on to improve greedy algorithm performance. but, aspnes et al. [fault-tolerant routing in peer-to-peer systems, in: proc. of acm 3st symp. on princ. of distr. comp. (podc 2002), vol. 31, 2002, pp. 223-232] shows that for a wide class of long-range link distributions, the expected length of the path computed by this algorithm is always ω(log2 n/(k2 log log n)).we design and analyze a new decentralized routing algorithm, in which nodes consult their neighbors near by, before deciding to whom forward the message. our algorithm uses similar amount of computational resources as kleinberg's greedy algorithm: it is easy to implement, visits o(log2 n/log2 (1 +k)) nodes on expectation and requires only θ(log2 n/log(1 +k)) bits of memory--note that [g.s. manku, m. naor, u. wieder, know thy neighbor's neighbor: the power of lookahead in randomized p2p networks, in: proc. of 36th acm stoc 2004, 2004, to appear], shows that any decentralized algorithm visits at least ω(log2 n/k) on expectation. our algorithm computes however a path of expected length o(log n (log log n)2/log2 (1 + k)) between any pair of nodes. our algorithm might fit better some human social behaviors (such as web browsing) and may also have successful applications to peer-to-peer networks where the length of the path along which the files are downloaded, is a critical parameter of the network performance.
simulation of one-dimensional cellular automata by uniquely parallel parsable grammars. a uniquely parsable grammar (upg) introduced by morita et al. (acta inform. 34 (1997) 389) is a special kind of generative grammar where parsing can be performed without backtracking. by extending a upg, a uniquely parallel parsable grammar (uppg) was proposed and its unique parallel parsability has been investigated. in this paper, we show any one-dimensional cellular automaton, as a parallel language recognition device, can be simply simulated by a parallel reduction in an equivalent uppg.
resource bounded symmetry of information revisited. the information contained in a string x about a string y is the difference between the kolmogorov complexity of y and the conditional kolmogorov complexity of y given x, i.e., i(x : y)=c(y)-c(y|x). the kolmogorov-levin theorem says that i(x : y) is symmetric up to a small additive term. we investigate if this property also holds for several versions of polynomial time-bounded kolmogorov complexity.we study symmetry of information for some variants of distinguishing complexity cd where cd(x) is the length of a shortest program which accepts x and only x. we show relativized worlds where symmetry of information does not hold in a strong way for deterministic and nondeterministic polynomial time distinguishing complexities cdpoly and cndpoly. on the other hand, for nondeterministic polynomial time distinguishing complexity with randomness, camdpoly, we show that symmetry of information holds for most pairs of strings in any set in np. our techniques extend work of buhrman et al. (language compression and pseudorandom generators, in: proc. 19th ieee conf. on computational complexity, ieee, new york, 2004, pp. 15-28) on language compression by am algorithms, and have the following application to the compression of samplable sources, introduced in trevisan et al. (compression of sample sources, in: proc. 19th ieee conf. on computational complexity, ieee, new york, 2004, pp. 1-15): any element x in the support of a polynomial time samplable source x can be given a description of size - log pr[x = x] + o(log3 n), from which x can be recovered by an am algorithm.
large triangles in the -dimensional unit cube. we consider a variant of heilbronn's triangle problem by asking for a distribution of n points in the d-dimensional unit cube [0, 1]d such that the minimum (two-dimensional) area of a triangle among these n points is as large as possible. denoting by δdoff-line (n) and δdon-line (n) the supremum of the minimum area of a triangle among n points over all distributions of n points in [0, 1]d for the off-line and the on-line situation, respectively, for fixed dimension d ≥ 2 we show that c1ċ(log n)1/(d-1)/n2/(d-1) ≤ δdoff-line(n) ≤ c'1/n2/d and c2/n2/(d-1) ≤ δdon-line (n) ≤ c'2/n2/d for constants c1, c2, c'1,c'2 > 0 which depend on d only. moreover, we provide a deterministic polynomial time algorithm that achieves the lower bound ω((log n)1/(d-1))/n2/(d-1)) on the minimum area of a triangle among n points in [0, 1]d in the off-line case.
neural circuits for pattern recognition with small total wire length. one of the most basic pattern recognition problems is whether a certain local feature occurs in some linear array to the left of some other local feature. we construct in this article circuits that solve this problem with an asymptotically optimal number of threshold gates. furthermore it is shown that much fewer threshold gates are needed if one employs in addition a small number of winner-take-all gates. in either case the circuits that are constructed have linear or almost linear total wire length, and are therefore not unrealistic from the point of view of physical implementations.
intrinsic reasoning about functional programs ii: unipolar induction and primitive-recursion. we continue from (ann. pure appl. logic 114 (2002) 117) our study of reasoning about recursion equations in rudimentary theories for inductive data, dubbed intrinsic theories. we show that the functions that are provable using unipolar induction are precisely the primitive-recursive functions, where we call an instance of induction unipolar if data pledicates do not occur in the induction formula both positively and negatively.two special cases of this result are well known, namely induction over σ10 and π10. here, however, induction formulas may have unrestricted quantifier alternations as long as those quantifiers that are relativized to data do not violate the prescribed restriction. the main technical challenge is in showing that the functions provable by unipolar induction, even in classical logic, are primitive-recursive.the result is generic with respect to the underlying inductive data, suggesting a potentially useful formalization of primitive-recursive mathematics.
competitive caching of query results in search engines. we study the problem of caching query result pages in web search engines. popular search engines receive millions of queries per day, and for each query, return a result page to the user who submitted the query. the user may request additional result pages for the same query, submit a new query, or quit searching altogether. an efficient scheme for caching query result pages may enable search engines to lower their response time and reduce their hardware requirements.this work studies query result caching within the framework of the competitive analysis of algorithms. we define a discrete time stochastic model for the manner in which queries are submitted to search engines by multiple user sessions. we then present an adaptation of a known online paging scheme to this model. the expected number of cache misses of the resulting algorithm is no greater than 4 times the expected number of misses that any online caching algorithm will experience under our specific model of query generation.
approximate pattern matching and transitive closure logics. a sartorial query language facilitates the formulation of queries to a (string) database. one step towards an implementation of such a query language can be taken by defining a logical formalism expressing a known solution for the particular problem at hand. the simplicity of the logic is a desired property, because the simpler the logic that the query language is based on, the more efficiently it can be implemented. we introduce a logical formalism for expressing approximate pattern matching. the formalism uses properties of the dynamic programming approach; a minimizing path of a dynamic programming table is expressed by using a formula in an extension of first order logic (fo). we consider the well-known problems of k-mismatches and k-differences. assuming first that k is given as a part of the input, those problems are expressed by using deterministic transitive closure logic (fo(dtc)) and transitive closure logic (fo(tc)), respectively. we show how to adapt the formalisms to allow individual costs for the editing operations, and consider music information retrieval (mir) as a case study.we believe that in the general case k-differences is not expressible in fo(dtc). however, we show that proving this is at least as hard as separating logspace from nlogspace. on the other hand, we show that if k is fixed, the k-differences problem can be expressed by an fo(dtc) formula.
the drawability problem for minimum weight triangulations. a graph is minimum weight drawable if it admits a straight-line drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. we study the problem of characterizing those graphs that are minimum weight drawable. our contribution is twofold: we show that there exist infinitely many triangulations that are not minimum weight drawable. furthermore, we present non-trivial classes of triangulations that are minimum weight drawable, along with corresponding linear time algorithms that take as input any graph from one of these classes and produce as output such a drawing. one consequence of our work is the construction of triangulations that are minimum weight drawable but not delaunay drawable - that is, not drawable as a delaunay triangulatio
category theory for operational semantics. we use the concept of a distributive law of a monad over a copointed endofunctor to define and develop a reformulation and mild generalisation of turi and plotkin's notion of an abstract operational rule. we make our abstract definition and give a precise analysis of the relationship between it and turi and plotkin's definition. following tuff and plotkin, our definition, suitably restricted, agrees with the notion of a set of gsos-rules, allowing one to construct both an operational model and a canonical, internally fully abstract denotational model. going beyond turi and plotkin, we construct what might be seen as large-step operational semantics from small-step operational semantics and we show how our definition allows one to combine distributive laws, in particular accounting for the combination of operational semantics with congruences.
hierarchical structures in sturmian dynamical systems. the paper is concerned with hierarchical stuctures in subshifis over a finite alphabet. in particular, we present a hierarchy-based approach to sturmian systems. this approach is then used to characterize the linearly repetitive sturmian systems (among the sturmian systems) by uniform positivity of certain weights. more generally, we discuss various bounds on weights and their relationship.finally, we combine hierarchies and bounds on a weights to study a thermodynamic formalism for lattice gas models associated to arbitrary linearly repetitive subshifts.
cross-monotonic cost sharing methods for connected facility location games. we present cost sharing methods for connected facility location games that are cross-monotonic and competitive and that recover a constant fraction of the cost of the constructed solution. the novelty of this paper is that we use randomized algorithms and that we share the expected cost among the participating users. as a consequence, our cost sharing methods are simple and achieve attractive approximation ratios. we also provide a primal-dual cost sharing method for the connected facility location game with opening costs.
towards a dynamical model for wireless sensor networks. in this paper we introduce two dynamical models for a broadcast process in wireless sensor networks. we obtain a convergent martingale sequence for the two models. to our knowledge, such martingales were unknown previously. we look at the formal models using the formalisms of martingales, dynamical systems and markov chains, each formalism providing complementary and coherent information with each other. the dynamics of both models are comparable and are validated in their domain of application with numerical simulation of wireless sensor networks. we make explicit the situations where the models are realistic. we also provide a formal analysis of the quasi-stationary distribution associated to the markov chain corresponding to the second model proposed.
a formal model of real-time program compilation. program compilation can be formally defined as a sequence of equivalence-preserving transformations, or refinements, from high-level language programs to assembler code. recent models also incorporate timing properties, but the resulting formalisms are intimidatingly complex. here we take advantage of a new, simple model of real-time refinement, based on predicate transformer semantics, to present a straightforward compilation formalism that incorporates real-time constraints.
a theory for execution-time derivation in real-time programs. we provide an abstract command language for real-time programs and outline how a partial correctness semantics can be used to compute execution times. the notions of a timed command, refinement of a timed command, the command traversal condition, and the worst-case and best-case execution time of a command are formally introduced and investigated with the help of an underlying weakest liberal precondition semantics. the central result is a theory for the computation of worst-case and best-case execution times from the underlying semantics based on supremum and infimum calculations. the framework is applied to the analysis of a message transmitter program and its implementation.
refinement and state machine abstraction. precise module interface specifications are essential in modular software development. the role of state in these specifications has been the issue of some debate and is central to the notion of data refinement. in previous work, hoffman and strooper introduce a state-abstraction lattice that defines a partial order on specifications for deterministic and complete languages. they use this lattice to define a notion of state abstractness and show that this intuitive notion corresponds to the use of the terms "abstract" and "concrete" as used in data-refinement proofs. in this paper, we extend this work for a class of specifications and languages that we call demonic and semi-deterministic. we also introduce a notion of backward refinement and prove that backward refinement together with the common forward refinement of vdm and z form a sound and complete refinement technique with respect to a partial order on languages defined by demonic specifications. we illustrate the ideas using simple languages and specifications. copyright 2001 elsevier science b.v.
a constructive algorithm for finding the exact roots of polynomials with computable real coefficients. in this paper we will show that it is possible to generate the roots of monic polynomials with computable real coefficients as computable complex numbers. a result from constructive analysis has already shown that the roots are computable numbers; however, because the proof is non-constructive it does not provide an effective method for finding the roots. in this work we combine two extra stages to a standard numerical algorithm: an exact error analysis, and a method for aligning sets of complex rational numbers so that the result is a set of computable complex numbers. the method of effectivization is of interest as it can be used in other situations where an algorithm will work with rational approximations, but comparison operations prevent its use with computable numbers.
using pvs to validate the algorithms of an exact arithmetic. the whole point of exact arithmetic is to generate answers to numeric problems, within some user-specified error. an implementation of exact arithmetic is therefore of questionable value, if it cannot be shown that it is generating correct answers. in this paper, we show that the algorithms used in an exact real arithmetic are correct. a program using the functions defined in this paper has been implemented in 'c' (a haskell version of which we provide as an appendix), and we are now convinced of its correctness. the table presented at the end of the paper shows that performing these proofs found three logical errors which had not been discovered by testing. one of these errors was only detected when the theorems were validated with pvs.
the limitedness problem on distance automata: hashiguchi's method revisited. hashiguchi has studied the limitedness problem of distance automata (da) in a series of paper [(j. comput. system sci. 24 (1982) 233; theoret. comput. sci. 72 (1990) 27; theoret. comput. sci. 233 (2000) 19)]. the distance of a da can be limited or unbounded. given that the distance of a da is limited, hashiguchi has proved in hashiguchi (2000) that the distance of the automaton is bounded by 24n3+n lg(n+2)+n, where n is the number of states. in this paper, we study again hashiguchi's solution to the limitedness problem. we have made a number of simplification and improvement on hashiguchi's method. we are able to improve the upper bound to 23n3+n lg n+n-1.
an efficient algorithm for online square detection. a square is a string that can be divided into two identical substrings. the problem of square detection has found applications in areas such as bioinformatics and data compression. there are many offline algorithms for the problem. in this paper, we give the first online algorithm for deciding whether a string contains a square. our algorithm runs in total o(h log2 h) time where h is the length of the longest prefix of the input string that does not contain a square.
on a conjecture about finite fixed points of morphisms. a conjecture of m. billaud is: given a word w, if, for each letter x occurring in w, the word obtained by erasing all the occurrences of x in w is a fixed point of a nontrivial morphism fx, then w is also a fixed point of a non-trivial morphism. we prove that this conjecture is equivalent to a similar one on sets of words. using this equivalence, we solve these conjectures in the particular case where each morphism fx has only one expansive letter.
newton's method with deflation for isolated singularities of polynomial systems. we present a modification of newton's method to restore quadratic convergence for isolated singular solutions of polynomial systems. our method is symbolic-numeric: we produce a new polynomial system which has the original multiple solution as a regular root. using standard bases, a tool for the symbolic computation of multiplicities, we show that the number of deflation stages is bounded by the multiplicity of the isolated root. our implementation performs well on a large class of applications.
performance evaluation for energy efficient topologic control in ad hoc wireless networks. minimizing total energy to keep an ad hoc wireless network symmetrically connected is an np-hard problem. recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. their performance ratios are established through estimations of the least upper bound ρk for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. in this paper, we determine the exact value of ρk for all k.
a 3d graphical representation of dna sequences and its application. a 3d graphical representation of dna sequences has been derived from mathematical denotation of dna sequence. the 3d graphical representation also avoids loss of information accompanying alternative 2d and 3d representation in which the curve standing for dna overlaps and intersects itself. the geometrical centers of the 3d graph of dna sequences indicate the distribution of base frequencies. an interesting phenomenon is observed for goat and gallus β-globin genomes with high g+c content. the examination of similarities/dissimilarities among the coding sequences of the first exon of β-globin gene of different species illustrates the utility of the approach.