waashk/dblp huggingface dataset:
multicommodity flows over time: efficient algorithms and complexity. flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g. the internet) and financial flows. the common characteristic are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks. while the 'maximum s-t-flow over time' problem can be solved efficiently and 'min-cost flows over time' are known to be np-hard, the complexity of (fractional) 'multicommodity flows over time' has been open for many years. we prove that this problem is np-hard, even for series-parallel networks, and present new and efficient algorithms under certain assumptions on the transit times or on the network topology. as a result, we can draw a complete picture of the complexity landscape for flow over time problems.
complexity results on branching-time pushdown model checking. the model checking problem of pushdown systems (pmc problem, for short) against standard branching temporal logics has been intensively studied in the literature. in particular, for the modal @m-calculus, the most powerful branching temporal logic used for verification, the problem is known to be exptime-complete (even for a fixed formula). the problem remains exptime-complete also for the logic ctl, which corresponds to a fragment of the alternation-free modal @m-calculus. for the logic ctl^*, the problem is known to be in 2exptime. in this paper, we show that the complexity of the pmc problem for ctl^* is in fact 2exptime-complete. moreover, we give a new optimal algorithm to solve this problem based on automata theoretic techniques. finally, we prove that the program complexity of the pmc problem against ctl (i.e., the complexity of the problem in terms of the size of the system) is exptime-complete.
ultraproducts and possible worlds semantics in institutions. we develop possible worlds (kripke) semantics at the categorical abstract model theoretic level provided by the so-called 'institutions'. our general abstract modal logic framework provides a method for systematic kripke semantics extensions of logical systems from computing science and logic. we also extend the institution-independent method of ultraproducts of [r. diaconescu, institution-independent ultraproducts, fundamenta informaticae 55 (3-4) (2003) 321-348] to possible worlds semantics and prove a fundamental preservation result for abstract modal satisfaction. as a consequence we develop a generic compactness result for possible worlds semantics.
losing recognizability. we consider the ranked alphabet @s consisting of a binary symbol. we give a rewrite system r over @s such that r effectively preserves recognizability on any ranked alphabet obtained by adding finitely many nullary symbols to @s. however, r does not preserve recognizability on the ranked alphabet obtained by adding one unary and one nullary symbol to @s.
decoding interleaved reed-solomon codes over noisy channels. we consider error correction over the non-binary symmetric channel (nbsc) which is a natural probabilistic extension of the binary symmetric channel (bsc). we propose a new decoding algorithm for interleaved reed-solomon codes that attempts to correct all ''interleaved'' codewords simultaneously. in particular, interleaved encoding gives rise to multi-dimensional curves and more specifically to a variation of the polynomial reconstruction problem, which we call simultaneous polynomial reconstruction. we present and analyze a novel probabilistic algorithm that solves this problem. our construction yields a decoding algorithm for interleaved rs codes that allows efficient transmission arbitrarily close to the channel capacity in the nbsc model.
generalising automaticity to modal properties of finite structures. we introduce a complexity measure of modal properties of finite structures which generalises the automaticity of languages. it is based on graph-automata-like devices called labelling systems. we define a measure of the size of a structure that we call rank, and show that any modal property of structures can be approximated up to any fixed rank n by a labelling system. the function that takes n to the size of the smallest labelling system doing this is called the labelling index of the property. we demonstrate that this is a useful and fine-grained measure of complexity and show that it is especially well suited to characterise the expressive power of modal fixed-point logics. from this we derive several separation results of modal and non-modal fixed-point logics, some of which are already known whereas others are new.
operational semantics for petri net components. we propose a calculus for marked labelled nets (components), with places and transitions as atoms and merge, addition, fusion and relabelling as operators. the operators are defined using graph-based transformations; each net can be represented by a term. next, we define both a step semantics for nets and a plotkin-style sos semantics for net terms and show their equivalence. in the semantics, both state-oriented and event-oriented properties of components can be expressed. we give a few rules for reducing components to smaller equivalent ones.
strong planning under uncertainty in domains with numerous but identical elements (a generic approach). the typical ai problem is that of making a plan of the actions to be performed by a robot so that the robot could get into a set of final situations, if it started with a certain initial situation. the planning problem is known to be generally very complex. even within the case of 'well-balanced' actions, strong planning under uncertainty about the effects of actions, or games such as 'robot against nature', is exptime-complete. as a result, ai planners are very sensitive to the number of the variables involved in making a plan, the inherent symmetry of the problem, and the nature of the logical formalisms being used. this paper shows that linear logic provides a convenient and adequate tool for representing strong and weak planning problems in non-deterministic domains. a particular focus of this paper is on planning problems with an unbounded number of functionally identical objects. we show that for such problems linear logic is especially effective and leads to a dramatic contraction of the search space from exponential to polynomial in size. we employ the ability of linear logic to reason about multisets, which in this instance are created by identifying several distinct objects as being functionally equivalent for the problem at hand (think of a number of balls, each of which must be moved to some new location - the balls are distinct, but are functionally equivalent for the problem). in linear logic terms, we establish a clear syntactic condition that allows us to show that solving a generic planning problem where there is only one generic object, directly implies a solution to the original real planning problem over several real objects, the isomorphic copies of the generic object. moreover, this correspondence also guarantees to produce a real solution that works in polynomial time.
local rule substitutions and stepped surfaces. substitutions on words, i.e., non-erasing morphisms of the free monoid, are simple combinatorial objects which produce infinite words by iteratively replacing letters by words. this paper introduces a notion of substitution acting on multi-dimensional words, namely local rule substitutions. roughly speaking, local rules play for multi-dimensional words the role played by the concatenation product for substitutions on words. we then particularly focus on the local rule substitutions which act on the two-dimensional words coding stepped surfaces, and we show that a wide class of them can be derived from generalized substitutions.
extension of the decidability of the marked pcp to instances with unique blocks. in the post correspondence problem (pcp) an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists a nonempty word w such that h(w)=g(w). here we prove that the pcp is decidable for instances with unique blocks using the decidability of the marked pcp. also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. these results establish a new and larger class of decidable instances of the pcp, including the class of marked instances.
on the cover time and mixing time of random geometric graphs. the cover time and mixing time of graphs has much relevance to algorithmic applications and has been extensively investigated. recently, with the advent of ad hoc and sensor networks, an interesting class of random graphs, namely random geometric graphs, has gained new relevance and its properties have been the subject of much study. a random geometric graph g(n,r) is obtained by placing n points uniformly at random on the unit square and connecting two points iff their euclidean distance is at most r. the phase transition behavior with respect to the radius r of such graphs has been of special interest. we show that there exists a critical radius r"o"p"t such that for any r>=r"o"p"tg(n,r) has optimal cover time of @q(nlogn) with high probability, and, importantly, r"o"p"t=@q(r"c"o"n) where r"c"o"n denotes the critical radius guaranteeing asymptotic connectivity. moreover, since a disconnected graph has infinite cover time, there is a phase transition and the corresponding threshold width is o(r"c"o"n). on the other hand, the radius required for rapid mixing r"r"a"p"i"d=@w(r"c"o"n), and, in particular, r"r"a"p"i"d=@q(1/poly(logn)). we are able to draw our results by giving a tight bound on the electrical resistance and conductance of g(n,r) via certain constructed flows.
factor versus palindromic complexity of uniformly recurrent infinite words. we study the relation between the palindromic and factor complexity of infinite words. we show that for uniformly recurrent words one has p(n)+p(n+1)@?@dc(n)+2, for all n@?n. for a large class of words this is a better estimate of the palindromic complexity in terms of the factor complexity than the one presented in [j.-p. allouche, m. baake, j. cassaigne, d. damanik, palindrome complexity, theoret. comput. sci. 292 (2003) 9-31]. we provide several examples of infinite words for which our estimate reaches its upper bound. in particular, we derive an explicit prescription for the palindromic complexity of infinite words coding r-interval exchange transformations. if the permutation @p connected with the transformation is given by @p(k)=r+1-k for all k, then there is exactly one palindrome of every even length, and exactly r palindromes of every odd length.
discrete random variables over domains. in this paper we initiate the study of discrete random variables over domains. our work is inspired by that of daniele varacca, who devised indexed valuations as models of probabilistic computation within domain theory. our approach relies on new results about commutative monoids defined on domains that also allow actions of the non-negative reals. using our approach, we define two such families of real domain monoids, one of which allows us to recapture varacca's construction of the plotkin indexed valuations over a domain. each of these families leads to the construction of a family of discrete random variables over domains, the second of which forms the object level of a continuous endofunctor on the categories rb (domains that are retracts of bifinite domains), and on fs (domains where the identity map is the directed supremum of deflations finitely separated from the identity). the significance of this last result lies in the fact that there is no known category of continuous domains that is closed under the probabilistic power domain, which forms the standard approach to modelling probabilistic choice over domains. the fact that rb and fs are cartesian closed and also are closed under a power domain of discrete random variables means we can now model, e.g. the untyped lambda calculus extended with a probabilistic choice operator, implemented via random variables.
on dynamic bit-probe complexity. this work present several advances in the understanding of dynamic data structures in the bit-probe model: *we improve the lower bound record for dynamic language membership problems to @w((lgnlglgn)^2). surpassing @w(lgn) was listed as the first open problem in a survey by miltersen. *we prove a bound of @w(lgnlglglgn) for maintaining partial sums in z/2z. previously, the known bounds were @w(lgnlglgn) and o(lgn). *we prove a surprising and tight upper bound of o(lgnlglgn) for the greater-than problem, and several predecessor-type problems. we use this to obtain the same upper bound for dynamic word and prefix problems in group-free monoids. we also obtain new lower bounds for the partial-sums problem in the cell-probe and external-memory models. our lower bounds are based on a surprising improvement of the classic chronogram technique of fredman and saks [michael l. fredman, michael e. saks, the cell probe complexity of dynamic data structures, in: proc. 21st acm symposium on theory of computing stoc, 1989, pp. 345-354], which makes it possible to prove logarithmic lower bounds by this approach. before the work of m. pa@?trascu and demaine [mihai pa@?trascu, erik d. demaine, logarithmic lower bounds in the cell-probe model, siam journal on computing 35 (4) (2006) 932-963. see also soda'04 and stoc'04], this was the only known technique for dynamic lower bounds, and surpassing @w(lgnlglgn) was a central open problem in cell-probe complexity.
new up-to techniques for weak bisimulation. up-to techniques have been introduced to enhance the bisimulation proof method for establishing bisimilarity results. while up-to techniques for strong bisimilarity are well understood, the irregularities that appear in the weak case make it difficult to give a unified presentation. we propose a uniform and modular theory of up-to techniques for weak bisimulation that captures most of the existing proof technology and introduces new techniques. some proofs rely on nontrivial-and new-commutation results based on termination guarantees. all results presented in this paper have been formally proved using the coq proof assistant.
functional stepped surfaces, flips, and generalized substitutions. a substitution is a non-erasing morphism of the free monoid. the notion of multidimensional substitution of non-constant length acting on multidimensional words is proved to be well-defined on the set of two-dimensional words related to discrete approximations of irrational planes. such a multidimensional substitution can be associated with any usual unimodular substitution. the aim of this paper is to extend the domain of definition of such multidimensional substitutions to functional stepped surfaces. one central tool for this extension is the notion of flips acting on tilings by lozenges of the plane.
recursively defined metric spaces without contraction. in this paper we use the theory of accessible categories to find fixed points of endofunctors on the category of 1-bounded complete metric spaces and nonexpansive functions. in contrast to previous approaches, we do not assume that the endofunctors are locally contractive, and our results do not depend on banach's fixed-point theorem. our approach is particularly suitable for constructing models of systems that feature quantitative data. for instance, using the kantorovich metric on probability measures we construct a quantitative model for probabilistic transition systems. the metric in our model can reasonably be seen as measuring the behavioural distance between states of the system; it depends exclusively on the transition probabilities and not on an arbitrary discount factor.
a faster combinatorial approximation algorithm for scheduling unrelated parallel machines. we consider the problem of scheduling n independent jobs on m unrelated parallel machines without preemption. job i takes processing time p"i"j on machine j, and the total time used by a machine is the sum of the processing times for the jobs assigned to it. the objective is to minimize makespan. the best known approximation algorithms for this problem compute an optimum fractional solution and then use rounding techniques to get an integral 2-approximation. in this paper we present a combinatorial approximation algorithm that matches this approximation quality. it is much simpler than the previously known algorithms and its running time is better. this is the first time that a combinatorial algorithm always beats the interior point approach for this problem. our algorithm is a generic minimum cost flow algorithm, without any complex enhancements, tailored to handle unsplittable flow. it pushes unsplittable jobs through a two-layered bipartite generalized network defined by the scheduling problem. in our analysis, we take advantage from addressing the approximation problem directly. in particular, we replace the classical technique of solving the lp-relaxation and rounding afterwards by a completely integral approach. we feel that this approach will be helpful also for other applications.
transposition invariant words. we define an operation called transposition on words of fixed length. this operation arises naturally when the letters of a word are considered as entries of a matrix. words that are invariant with respect to transposition are of special interest. it turns out that transposition invariant words have a simple interpretation by means of elementary group theory. this leads us to investigate some properties of the ring of integers modulo n and primitive roots. in particular, we show that there are infinitely many prime numbers p with a primitive root dividing p+1 and infinitely many prime numbers p without a primitive root dividing p+1. we also consider the orbit of a word under transposition.
on alpha-adic expansions in pisot bases. we study @a-adic expansions of numbers, that is to say, left infinite representations of numbers in the positional numeration system with the base @a, where @a is an algebraic conjugate of a pisot number @b. based on a result of bertrand and schmidt, we prove that a number belongs to q(@a) if and only if it has an eventually periodic @a-adic expansion. then we consider @a-adic expansions of elements of the ring z[@a^-^1] when @b satisfies the so-called finiteness property (f). we give two algorithms for computing these expansions - one for positive and one for negative numbers. in the particular case that @b is a quadratic pisot unit satisfying (f), we inspect the unicity and/or multiplicity of @a-adic expansions of elements of z[@a^-^1]. we also provide algorithms to generate @a-adic expansions of rational numbers in that case.
infinite unfair shuffles and associativity. we consider a general shuffling operation for finite and infinite words which is not necessarily fair. this means that it may be the case that in a shuffle of two words, from some point onwards, one of these words prevails ad infinitum even though the other word still has letters to contribute. prefixes and limits of shuffles are investigated, leading to a characterization of general shuffles in terms of shuffles of finite words, a result which does not hold for fair shuffles. associativity of shuffling is an immediate corollary.
a tight linear bound on the synchronization delay of bijective automata. reversible cellular automata (rca) are models of massively parallel computation that preserve information. we generalize these systems by introducing the class of ^@w^@wbijective finite automata. it consists of those finite automata where for any bi-infinite word there exists a unique path labelled by that word. these systems are strictly included in the class of local automata. although the synchronization delay of an n-state local automaton is known to be @q(n^2) in the worst case, we prove that in the case of ^@w^@wbijective finite automata the synchronization delay is at most n-1. based on this we prove that for a one-dimensional n-state rca where the neighborhood consists of m consecutive cells, the neighbourhood of the inverse automaton consists of at most n^m^-^1-(m-1) cells. similar bounds are obtained also in [e. czeizler, j. kari, a tight linear bound on the neighborhood of inverse cellular automata, in: proceedings of icalp 2005, in: lncs, vol. 3580, 2005, pp. 410-420] but here the result comes as a direct consequence of the more general result. we also construct examples of rca with large inverse neighbourhoods proving that the upper bounds provided here are the best possible in the case m=2.
faster algorithms for finding lowest common ancestors in directed acyclic graphs. we present two new methods for finding a lowest common ancestor (lca) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. the first method is surprisingly natural and solves the all-pairs lca problem for the input dag on n vertices and m edges in time o(nm). the second method relies on a novel reduction of the all-pairs lca problem to the problem of finding maximum witnesses for boolean matrix product. we solve the latter problem (and hence also the all-pairs lca problem) in time o(n^2^+^@l), where @l satisfies the equation @w(1,@l,1)=1+2@l and @w(1,@l,1) is the exponent of the multiplication of an nxn^@l matrix by an n^@lxn matrix. by the currently best known bounds on @w(1,@l,1), the running time of our algorithm is o(n^2^.^5^7^5). our algorithm improves the previously known o(n^2^.^6^8^8) time-bound for the general all-pairs lca problem in dags by bender et al. our additional contribution is a faster algorithm for solving the all-pairs lowest common ancestor problem in dags of small depth, where the depth of a dag is defined as the length of the longest path in the dag. for all dags of depth at most h@?n^@a, where @a~0.294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two nxn matrices, that is, o(n^@w); we also prove that this running time is optimal even for dags of depth 1. for dags with depth h>n^@a, the running time of our algorithm is at most o(n^@w@?h^0^.^4^6^8). this algorithm is faster than our algorithm for arbitrary dags for all values of h@?n^0^.^4^2.
the quantum query complexity of the abelian hidden subgroup problem. simon, in his focs'94 paper, was the first to show an exponential gap between classical and quantum computation. the problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. we study simon's problem from the point of view of quantum query complexity and give here a first non-trivial lower bound on the query complexity of a hidden subgroup problem, namely simon's problem. more generally, we give a lower bound which is optimal up to a constant factor for any abelian group.
a geometrical characterization of factors of multidimensional billiard words and some applications. we consider billiard words in alphabets with k>2 letters. such words are associated with some k-dimensional positive vector @a->=(@a"1,@a"2,...,@a"k). the language of these words is already known in the usual case, i.e. when the @a"j are linearly independent over q and so for their inverses. here we study the language of these words when there exist some linear relationships. we give a new geometrical characterization of the factors of billiard words. as a consequence, we get some results on the associated language, and on the complexity and palindromic complexity of these words. the situation is quite different from the usual case. the languages of two distinct billiard words with the same direction generally have a finite intersection. as examples, we get some standard billiard words of three letters without any palindromic factor of even length, or billiard words of three letters whose palindromic factors have a bounded length. these results are obtained by geometrical methods.