waashk/dblp huggingface dataset:
expressive power of sql. it is a folk result in database theory that sql cannot express recursive queries such as reachability; in fact, a new construct was added to sql3 to overcome this limitation. however, the evidence for this claim is usually given in the form of a reference to a proof that relational algebra cannot express such queries. sql, on the other hand, in all its implementations has three features that fundamentally distinguish it from relational algebra: namely, grouping, arithmetic operations, and aggregation.in the past few years, most questions about the additional power provided by these features have been answered. this paper surveys those results, and presents new simple and self-contained proofs of the main results on the expressive power of sql. somewhat surprisingly, tiny differences in the language definition affect the results in a dramatic way: under some very natural assumptions, it can be proved that sql cannot define recursive queries, no matter what aggregate functions and arithmetic operations are allowed. but relaxing these assumptions just a tiny bit makes the problem of proving expressivity botmds for sql as hard as some long-standing open problems in complexity theory.
lower bounds for invariant queries in logics with counting. we study the expressive power of counting logics in the presence of auxiliary relations such as orders and preorders. the simplest such logic is the first-order logic with counting. this logic captures the complexity class tc0 over ordered structures. we also consider first-order logic with arbitrary unary quantifiers and with infinitary extensions.we start by giving a simple direct proof that first-order logic with counting, in the presence of pre-orders that are almost-everywhere linear orders, cannot express the transitive closure of a binary relation. the proof is based on locality of formulae. we then show that the technique cannot be extended to linear orders. we further show that this result does not say anything about the power of invariant queries in first-order logic with counting vs. the class tc0, in the presence of these preorders.in the second part of the paper, we prove a separation result showing that, for all the counting logics above, a linear order is more powerful than a preorder that is a linear order almost everywhere. in fact, we prove that the expressive power of invariant queries in the presence of such preorders can be characterized by a property normally associated with first-order definability over unordered structures. we do this by using locality techniques from finite-model theory. however, as some standard notions of locality fail in this setting, we have to modify them to prove the main result.
an evaluation function for the game of amazons. amazons is a fascinating game that shares properties of chess and go. designing a computer program that plays amazons on the level of human experts and beyond is a real challenge. this article emphasizes the secret of such a program, viz. its evaluation function. we describe the function by using explicit formulas, we mention the ideas and goals behind these formulas, we discuss possible refinements, and study in detail methods for special endgame problems. by analyzing a tournament game of amazong against the threefold computer world champion 8qp we illustrate how the new features of our evaluation function can lead to victory.
k-center problems with minimum coverage. in this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. this problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. we study three variants of this problem, all of which are shown to be n p-hard. in-approximation hardness and approximation algorithms with factors equal or close to the best lower bounds are provided. generalizations, including vertex costs and vertex weights, are also studied.
fast inversion of triangular toeplitz matrices. in this paper, we present an approximate inversion method for triangular toeplitz matrices based on trigonometric polynomial interpolation. to obtain an approximate inverse of high accuracy for a triangular toeplitz matrix of size n, our algorithm requires two fast fourier transforms (ffts) and one fast cosine transform of 2n-vectors. we then revise the approximate method proposed by bini (siam j. comput. 13 (1984) 268). the complexity of the revised bini algorithm is two ffts of 2n-vectors.
towards area requirements for drawing hierarchically planar graphs. hierarchical graphs are an important class of graphs for modeling many real applications in software and information visualization. in this paper, we investigate area requirements for drawing hierarchically planar graphs regarding two different drawing standards. firstly, we show an exponential lower bound for the area needed for straight-line drawing of hierarchically planar graphs. the lower bound holds even for s-t hierarchical graphs without transitive arcs, in contrast to the results for upward planar drawing. this motivates our investigation of another drawing standard grid visibility representation, as a relaxation of straight-line drawing. an application of the existing results from upward drawing can guarantee a quadric drawing area for grid visibility representation but does not necessarily guarantee the minimum drawing area. motivated by this, we will present a new grid visibility drawing algorithm which is efficient and guarantees the minimum drawing area with respect to a given topological embedding. this implies that the area minimization problem is polynomial time solvable restricted to the class of graphs whose planar embeddings are unique. however, we can show that the problem of area minimization of grid visibility for hierarchically planar graphs is generally np-hard, even restricted to s-t graphs.
the super connectivity of the pancake graphs and the super laceability of the star graphs. a k-container c(u, v) of a graph g is a set of k-disjoint paths joining u to v. a k-container c(u, v) of g is a k*-container if it contains all the vertices of g. a graph g is k*-connected if there exists a k*-container between any two distinct vertices. let κ(g) be the connectivity of g. a graph g is super connected if g is i*-connected for all 1 ≤ i ≤ κ(g). a bipartite graph g is k*-laceable if there exists a k*-container between any two vertices from different parts of g. a bipartite graph g is super laceable if g is i*-laceable for all 1 ≤ i ≤ κ(g). in this paper, we prove that the n-dimensional pancake graph pn is super connected if and only if n ≠ 3 and the n-dimensional star graph sn is super laceable if and only if n ≠ 3.
graph bandwidth of weighted caterpillars. graph bandwidth minimization (gbm) is a classical and challenging problem in graph algorithms and combinatorial optimization. most of existing researches on this problem have focused on unweighted graphs. in this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars and general graphs. more specifically, we show that the gbm problem on caterpillars with hair-length at most 2 and the gbm problem on star-shape caterpillars are np-complete, and give a lower bound of the graph bandwidth for general weighted graphs. for caterpillars with hair-length at most 1, we present an o(n log n log(nwmax))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and wmax is the maximum wedge weight. for caterpillars with hair-length at most k, we give a k-approximation algorithm. for arbitrary caterpillars and general graphs, we give a heuristic algorithm and some experimental results. experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of clog(n) of the lower bound for a small number c, which is consistent with the inapproximability results of this problem (i.e., no constant approximation for the gbm problem unless p = np).
the complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. valiant (siam j. comput. 8 (1979) 410-421) showed that the problem of computing the number of simple s-t paths in graphs is #p-complete both in the case of directed graphs and in the case of undirected graphs. welsh (complexity: knots, colourings and counting, cambridge university press, cambridge, 1993, p. 17) asked whether the problem of computing the number of self-avoiding walks of a given length in the complete two-dimensional grid is complete for #p1, the tally-version of #p. this paper offers a partial answer to the question of welsh: it is #p-complete to compute the number of self-avoiding walks of a given length in a subgraph of a two-dimensional grid. several variations of the problem are also studied and shown to be #p-complete. this paper also studies the problem of computing the number of self-avoiding walks in a subgraph of a hypercube. similar completeness results are shown for the problem. by scaling the computation time to exponential, it is shown that computing the number of self-avoiding walks in hypercubes is a complete problem for #exp in the case when a subgraph of a hypercube is specified by its dimension and a boolean circuit that accepts the nodes.finally, this paper studies the complexity of testing whether a given word over the four-letter alphabet {u,d,l,r} represents a self-avoiding walk in a two-dimensional grid. a linear-space lower bound is shown for nondeterministic turing machines with a 1-way input head to make this test.
approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine. a batch machine is a machine that can process a number of jobs simultaneously as a batch, and the processing time of a batch is equal to the longest processing time of the jobs assigned to it. in this paper, we present a polynomial time approximation scheme (ptas) for scheduling a batch machine to minimize the total completion time with job release dates. also, we present a fully polynomial time approximation scheme (fptas) for scheduling an unbounded batch machine, which can process an arbitrary number of jobs simultaneously, to minimize the total weighted completion time with job release dates.
finitary pcf is not decidable. the question of the decidability of the observational ordering of finitary pcf was raised (jung and stoughton, in: m. bezem, j.f. groote (eds.), typed lambda calculi and applications, lecture notes in computer science, vol. 664, springer, berlin, 1993, pp. 230-244) to give mathematical content to the full abstraction problem for pcf (milner, theoret. comput. sci. 4 (1977) 1-22). we show that the ordering is in fact undecidable. this result places limits on how explicit a representation of the fully abstract model can be. it also gives a slight strengthening of the author's earlier result on typed ability (loader, in: a. anderson, m. zeleny (eds.), church memorial volume, kluwer academic press, dordrecht, to appear). copyright 2001 elsevier science b.v.
realizability of high-level message sequence charts: closing the gaps. we study the notion of safe realizability for high-level message sequence charts (hmscs) (proceedings of the 28th international colloquium on automata, languages and programming (icalp 2001), crete (greece), lecture notes in computer science, vol. 2076, springer, berlin, 2001, pp. 797-808). we show that safe realizability is expspace-complete for bounded hmscs but undecidable for the class of all hmscs. this solves two open problems from alur et al. moreover we prove that safe realizability is also expspace-complete for the larger class of globally-cooperative hmscs.
the complexity of tree automata and xpath on grammar-compressed trees. the complexity of various membership problems for tree automata on compressed trees is analyzed. two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts in a tree. several completeness results for the classes nl, p, and pspace are obtained. finally, the complexity of the evaluation problem for (structural) xpath queries on trees that are compressed via straight-line context-free tree grammars is investigated.
introducing va. this paper reports on a new software platform called vaucanson and dedicated to the computation with automata and transducers. its main feature is the capacity of dealing with automata whose labels may belong to various algebraic structures.the paper successively describes the main features of the vaucanson platform, including the fact that the very rich data structure used to implement automata does not weigh too much on the performance, shows how vaucanson allows to program algorithms on automata in a way which is very close to the mathematical expression of the algorithm and finally explains the main choices of the programming design that enable to achieve both genericity and efficiency.
derivatives of rational expressions with multiplicity. this paper addresses the problem of turning a rational (i.e. regular) expression into a finite automaton. we formalize and generalize the idea of "partial derivatives" introduced in 1995 by antimirov, in order to obtain a construction of an automaton with multiplicity from a rational expression describing a formal power series with coefficients in a semiring.we first define precisely what is such a rational expression with multiplicity and which hypothesis should be put on the semiring of coefficients in order to keep the usual identities.we then define the derivative of such a rational expression as a linear combination of expressions called derived terms and we show that all derivatives of a given expression are generated by a finite set of derived terms, that yields a finite automaton with multiplicity whose behaviour is the series denoted by the expression. we also prove that this automaton is a quotient of the standard (or glushkov) automaton of the expression. finally, we propose and discuss some possible modifications to our definition of derivation.
sequential? this paper is a survey where we try to organise the known answers to the question whether a given finite automaton with multiplicity in a semiring k is equivalent to a sequential, or input deterministic, one. we shall see that depending on k, the question goes from obvious to open, that the answer goes from yes to undecidable. we review results on sequentiality in the cases of series of finite image, of series with multiplicity in fields, and of series with multiplicity in idempotent semirings.
an alternative definition of splicing. in this paper, we propose a new definition of the language generated by a splicing system, motivated by both biochemical and mathematical considerations. the main feature of the new definition is that by applying a splicing rule, we not only create new strings, but also allow for the removal of the strings entering the rule. this behaviour seems to correspond better to biochemical reality and is in fact used as a tool in several experimental dna computations. we show that using this new definition, finite extended h systems can generate all recursively enumerable languages. even a weaker version of these h systems, defined using the new notion of delay, is shown to be strictly more powerful than h systems defined in the traditional way.
on-line parallel heuristics, processor scheduling and robot searching under the competitive framework. in this paper we investigate parallel searches on m concurrent rays for a point target t located at some unknown distance along one of the rays. a group of p agents or robots moving at unit speed searches for t. the search succeeds when an agent reaches the point t. given a strategy s the competitive ratio is the ratio of the time needed by the agents to find t using s and the time needed if the location of t had been known in advance. we provide a strategy with competitive ratio of 1 + 2(m/p - 1)(m/(m - p))m/p and prove that this is optimal. this problem has applications in multiple heuristic searches in ai as well as robot motion planning. the case p = 1 is known in the literature as the cow path problem.
a mathematical model for the tcp tragedy of the commons. this paper presents a novel mathematical model for the tcp tragedy of the commons, using game theory concepts. this tragedy may appear in a tcp/ip-based network when hosts do not respect the protocol rules and try to monopolize the shared network resources by using a selfish strategy. our model quantifies the effects of this evil behavior in a simple and standard network topology and allows to obtain some interesting results which we prove formally. finally, we validate the model results by comparing its predictions with a set of extensive simulations carried out using the ns network simulator.
specification, testing and implementation relations for symbolic-probabilistic systems. we consider the specification and testing of systems where probabilistic information is not given by means of fixed values but as intervals of probabilities. we will use an extension of the finite state machines model where choices among transitions labelled by the same input action are probabilistically resolved. we will introduce our notion of test and we will define how tests are applied to implementations under test. we will also present implementation relations to assess the conformance, up to a level of confidence, of an implementation to a specification. in order to define these relations we will take finite samples of executions of the implementation and compare them with the probabilistic constraints imposed by the specification. finally, we will give an algorithm for deriving sound and complete test suites.
error analysis in minimax trees. game tree search deals with the problems that arise, when computers play two-person-zero-sum-games such as chess, checkers, othello, etc. the greatest success of game tree search so far, was the victory of the chess machine 'deep blue' vs. g. kasparov (icca j. 20 (1997) 95), the best human chess player in the world at that time. in spite of the enormous popularity of computer chess and in spite of the successes of game tree search in game playing programs, we do not know much about a useful theoretical background that could explain the usefulness of (selective) search in adversary games.we introduce a combinatorial model, which allows us to model errors of a heuristic evaluation function, with the help of coin tosses. as a result, we can show that searching in a game tree will be 'useful' if, and only if, there are at least two leaf-disjoint strategies which prove the root value. in addition, we show that the number of leaf-disjoint strategies, contained in a game tree, determines the order of the quality of a heuristic minimax value. the model is integrated into the context of average-case analyses.
new approximation algorithm for rtile problem. for a given two-dimensional array of nonnegative numbers and a positive integer p we want to find a covering of the array with p tiles so as to minimize the weight of the heaviest tile. we present a 9/4-approximation linear-time algorithm for this problem, which improves on the previous best result.
monotone runs of uniformly distributed integer random variables: a probabilistic analysis. using a markov chain approach and a polyomino-like description, we study some asymptotic properties of monotone increasing runs of uniformly distributed integer random variables. we analyze the limiting trajectories, which after suitable normalization, lead to a brownian motion, the number of runs, which is asymptotically gaussian, the run length distribution, the hitting time to a large length k run, which is asymptotically exponential, and the maximum run length which is related to the gumbel extreme-value distribution function. a preliminary application to dna analysis is also given.
ascending runs of sequences of geometrically distributed random variables: a probabilistic analysis. using a markov chain approach and a polyomino-like description, we study some asymptotic properties of sequences of ascending runs of geometrically distributed random variables. we analyze the limiting trajectories, the number of runs and the run length distribution, the hitting time to a length k run and the maximum run length.
generalized covariances of multi-dimensional brownian excursion local times. expressions for the generalized covariances of multi-dimensional brownian excursion local times are derived from corresponding densities transforms. typical applications are moments of the cost of structures such as m/g/1 queue, random trees, markov stack or priority queue in knuth's model. brownian excursion area and a result of biane and yor are also revisited.
simulations among multidimensional turing machines. for all d ≥ 1 and all e > d, every deterministic multihead e-dimensional turing machine of time complexity t(n) can be simulated on-line by a deterministic multihead d-dimensional turing machine in time o(t(n)1+1/d-1/e(log t(n))o(1)). this simulation almost achieves the known lower bound ω(t(n)1+1/d-1/e) on the time required. furthermore, there is a deterministic d-dimensional machine with just two worktape heads that simulates the e-dimensional machine on-line in time o(t(n)1+1/d-1/delog t(n)). these simulations are interpreted in terms of dynamic embeddings among data structures.
semantic models for information flow. in the past, several definitions of information flow have been presented, based upon process algebras. unfortunately, all these appear to be either too weak--failing to identify certain subtle forms of information flow or too strong--indicating information flow when there is none. in this paper, we produce a definition that aims to overcome these shortcomings. we base our definition upon an operational model of csp that reasons about the ways in which nondeterministic choices can be resolved, and so is more discriminating than previous models. our definition of information flow is then that the behaviour of one agent can have some influence upon another agent's view of the system. this definition gives the expected results on all thought experiments tried to date, and also satisfies certain desirable properties.
any-world assumptions in logic programming. due to the usual incompleteness of information representation, any approach to assign a semantics to logic programs has to rely on a default assumption on the missing information. the stable model semantics, that has become the dominating approach to give semantics to logic programs, relies on the closed world assumption (cwa), which asserts that by default the truth of an atom is false. there is a second well-known assumption, called open world assumption (owa), which asserts that the truth of the atoms is supposed to be unknown by default. however, the cwa, the owa and the combination of them are extremal, though important, assumptions over a large variety of possible assumptions on the truth of the atoms, whenever the truth is taken from an arbitrary truth space.the topic of this paper is to allow any assignment (i.e. interpretation), over a truth space, to be a default assumption. our main result is that our extension is conservative in the sense that under the "everywhere false" default assumption (cwa) the usual stable model semantics is captured. due to the generality and the purely algebraic nature of our approach, it abstracts from the particular formalism of choice and the results may be applied in other contexts as well.