waashk/dblp huggingface dataset:
stationary algorithmic probability. kolmogorov complexity and algorithmic probability are defined only up to an additive resp. multiplicative constant, since their actual values depend on the choice of the universal reference computer. in this paper, we analyze a natural approach to eliminate this machine-dependence. our method is to assign algorithmic probabilities to the different computers themselves, based on the idea that ''unnatural'' computers should be hard to emulate. therefore, we study the markov process of universal computers randomly emulating each other. the corresponding stationary distribution, if it existed, would give a natural and machine-independent probability measure on the computers, and also on the binary strings. unfortunately, we show that no stationary distribution exists on the set of all computers; thus, this method cannot eliminate machine-dependence. moreover, we show that the reason for failure has a clear and interesting physical interpretation, suggesting that every other conceivable attempt to get rid of those additive constants must fail in principle, too. however, we show that restricting to some subclass of computers might help to get rid of some amount of machine-dependence in some situations, and the resulting stationary computer and string probabilities have beautiful properties.
three results on frequency assignment in linear cellular networks. in the frequency assignment problem we are given a graph representing a wireless network and a sequence of requests, where each request is associated with a vertex. each request has two more attributes: its arrival and departure times, and it is considered active from the time of arrival to the time of departure. we want to assign frequencies to all requests so that at each time step any two active requests associated with the same or adjacent vertices use different frequencies. the objective is to minimize the number of frequencies used. we focus exclusively on the special case of the problem when the underlying graph is a linear network (path). for this case, we consider both the offline and online versions of the problem, and we present three results. first, in the incremental online case, where the requests arrive over time, but never depart, we give an algorithm with an optimal (asymptotic) competitive ratio 43. second, in the general online case, where the requests arrive and depart over time, we improve the current lower bound on the (asymptotic) competitive ratio to 117. third, we prove that the offline version of this problem is np-complete.
definable transductions and weighted logics for texts. a text is a word together with an additional linear order on it. we study quantitative models for texts, i.e. text series which assign to texts elements of a semiring. we introduce an algebraic notion of recognizability following reutenauer and bozapalidis as well as weighted automata for texts combining an automaton model of lodaya and weil with a model of esik and nemeth. after that we show that both formalisms describe the text series definable in a certain fragment of weighted logics as introduced by droste and gastin. in order to do so, we study certain definable transductions and show that they are compatible with weighted logics.
linear logic by levels and bounded time complexity. we give a new characterization of elementary and deterministic polynomial time computation in linear logic through the proofs-as-programs correspondence. girard's seminal results, concerning elementary and light linear logic, achieve this characterization by enforcing a stratification principle on proofs, using the notion of depth in proof nets. here, we propose a more general form of stratification, based on inducing levels in proof nets by means of indices, which allows us to extend girard's systems while keeping the same complexity properties. in particular, it turns out that girard's systems can be recovered by forcing depth and level to coincide. a consequence of the higher flexibility of levels with respect to depth is the absence of boxes for handling the paragraph modality. we use this fact to propose a variant of our polytime system in which the paragraph modality is only allowed on atoms, and which may thus serve as a basis for developing lambda-calculus type assignment systems with more efficient typing algorithms than existing ones.
new algorithms for approximate nash equilibria in bimatrix games. we consider the problem of computing additively approximate nash equilibria in non-cooperative two-player games. we provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. we first provide a simpler algorithm, that achieves a 0.38197-approximation, which is exactly the same factor as the algorithm of daskalakis, mehta and papadimitriou. this algorithm is then tuned, improving the approximation error to 0.36392. our method is relatively fast and simple, as it requires solving only one linear program and it is based on using the solution of an auxiliary zero-sum game as a starting point. finally we also exhibit a simple reduction that allows us to compute approximate equilibria for multi-player games by using algorithms for two-player games.
itineraries of rigid rotations and diffeomorphisms of the circle. we examine the itinerary of 0@?s^1=r/z under the rotation by @a@?r@?q. the motivating question is: if we are given only the itinerary of 0 relative to i@?s^1, a finite union of closed intervals, can we recover @a and i? we prove that the itineraries do determine @a and i up to certain equivalences. then we present elementary methods for finding @a and i. moreover, if g:s^1->s^1 is a c^2, orientation preserving diffeomorphism with an irrational rotation number, then we can use the orbit itinerary to recover the rotation number up to certain equivalences.
priority algorithms for graph optimization problems. we continue the study of priority or ''greedy-like'' algorithms as initiated in borodin et al. (2003) [10] and as extended to graph theoretic problems in davis and impagliazzo (2009) [12]. graph theoretic problems pose some modeling problems that did not exist in the original applications of borodin et al. and angelopoulos and borodin (2002) [3]. following the work of davis and impagliazzo, we further clarify these concepts. in the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. we study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known ''greedy algorithms''.
simulation of one-way cellular automata by boolean circuits. we present a relationship between two major models of parallel computation: the one-way cellular automata and the boolean circuits. the starting point is the boolean circuit of small depth designed by ladner and fischer to simulate any rational transducer. we extend this construction to simulate one-way cellular automata by boolean circuits.
variations on a theme by akl and taylor: security and tradeoffs. in 1983, akl and taylor [cryptographic solution to a problem of access control in a hierarchy, acm transactions on computer systems 1 (3) (1983) 239-248] first suggested the use of cryptographic techniques to enforce access control in hierarchical structures. due to its simplicity and versatility, the scheme has been used, for more than twenty years, to implement access control in several different domains, including mobile agent environments and xml documents. however, despite its use over time, the scheme has never been fully analyzed with respect to security and efficiency requirements. in this paper we provide new results on the akl-taylor scheme and its variants. more precisely: *we provide a rigorous analysis of the akl-taylor scheme. we consider different key assignment strategies and prove that the corresponding schemes are secure against key recovery. *we show how to obtain different tradeoffs between the amount of public information and the number of steps required to perform key derivation in the proposed schemes. *we also look at the mackinnon et al. and harn and lin schemes and prove they are secure against key recovery. *we describe an akl-taylor based key assignment scheme with time-dependent constraints and prove the scheme efficient, flexible and secure. *we propose a general construction, which is of independent interest, yielding a key assignment scheme offering security w.r.t. key indistinguishability, given any key assignment scheme which guarantees security against key recovery. *finally, we show how to use our construction, along with our assignment strategies and tradeoffs, to obtain an akl-taylor scheme, secure w.r.t. key indistinguishability, requiring a constant amount of public information.
strong normalization property for second order linear logic. the paper contains the first complete proof of strong normalization (sn) for full second order linear logic (ll): girard's original proof uses a standardization theorem which is not proven. we introduce sliced pure structures (sps), a very general version of girard's proof-nets, and we apply to sps gandy's method to infer sn from weak normalization (wn). we prove a standardization theorem for sps: if wn without erasing steps holds for an sps, then it enjoys sn. a key step in our proof of standardization is a confluence theorem for sps obtained by using only a very weak form of correctness, namely acyclicity slice by slice. we conclude by showing how standardization for sps allows to prove sn of ll, using as usual girard's reducibility candidates.
an axiom system for sequence-based specification. this paper establishes an axiomatic foundation and a representation theorem for the rigorous, constructive process, called sequence-based specification, of deriving precise specifications from ordinary (informal) statements of functional requirements. the representation theorem targets a special class of mealy state machines, and algorithms are presented for converting from the set of sequences that define the specification to the equivalent mealy machine, and vice versa. since its inception, sequence-based specification has been effectively used in a variety of real applications, with gains reported in quality and productivity. this paper establishes the mathematical foundation independently of the process itself.
energy optimal schedules for jobs with multiple active intervals. in this paper, we study the scheduling problem of jobs with multiple active intervals. each job in the problem instance has n(n>=1) disjoint active time intervals where it can be executed and a workload characterized by the required number of cpu cycles. previously, people studied multiple interval job scheduling problem where each job must be assigned enough cpu cycles in one of its active intervals. we study a different practical version where the partial work done by the end of an interval remains valid and each job is considered finished if total cpu cycles assigned to it in all its active intervals reach the requirement. the goal is to find a feasible schedule that minimizes energy consumption. by adapting the algorithm for single interval jobs proposed in yao, demers and shenker (1995) [1], one can still obtain an optimal schedule. however, the two phases in that algorithm (critical interval finding and scheduling the critical interval) can no longer be carried out directly. we present polynomial time algorithms to solve the two phases for jobs with multiple active intervals and therefore can still compute the optimal schedule in polynomial time.
quantum implicit computational complexity. we introduce a quantum lambda calculus inspired by lafont's soft linear logic and capturing the polynomial quantum complexity classes eqp, bqp and zqp. the calculus is based on the ''classical control and quantum data'' paradigm. this is the first example of a formal system capturing quantum complexity classes in the spirit of implicit computational complexity - it is machine-free and no explicit bound (e.g., polynomials) appears in its syntax.
on stateless multihead automata: hierarchies and the emptiness problem. we look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. the transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition moves each head one cell left or right, or instructs it to stay. we show that stateless (k+4)-head two-way automata are more powerful than stateless k-head two-way automata. in the one-way case, we prove a tighter result: stateless (k+1)-head one-way automata are more powerful than stateless k-head one-way automata. finally, we show that the emptiness problem for stateless 2-head two-way automata is undecidable.
on lazy bin covering and packing problems. in this paper, we study two interesting variants of the classical bin packing problem, called lazy bin covering (lbc) and cardinality constrained maximum resource bin packing (ccmrbp) problems. for the offline lbc problem, we first prove the approximation ratio of the first-fit-decreasing and first-fit-increasing algorithms, then present an aptas. for the online lbc problem, we give a competitive analysis for the algorithms of next-fit, worst-fit, first-fit, and a modified harmonic"m algorithm. the ccmrbp problem is a generalization of the maximum resource bin packing (mrbp) problem boyar et al. (2006) [1]. for this problem, we prove that its offline version is no harder to approximate than the offline mrbp problem.
on graphs of central episturmian words. episturmian sequences are a natural extension of sturmian sequences to the case of finite alphabets of arbitrary cardinality. in this paper, we are interested in central episturmian words, or simply, epicentral words, i.e., the palindromic prefixes of standard episturmian sequences. an epicentral word admits a variety of faithful representations including as a directive word, as a certain type of period vector, as a parikh vector, as a certain type of fine and wilf extremal word, as a suitable modular matrix, and as a labeled graph. various interconnections between the different representations of an epicentral word are analyzed. in particular, we investigate the structure of the graphs of epicentral words proving some curious and surprising properties.
narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound. the k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most k different values are decided. it has been shown that any algorithm that solves the k-set agreement problem in synchronous systems that can suffer up to t crash failures requires @?tk@?+1 rounds in the worst case. it has also been shown that it is possible to design early deciding algorithms where no process decides and halts after min(@?fk@?+2,@?tk@?+1) rounds, where f is the number of actual crashes in a run (0@?f@?t). this paper explores a new direction to solve the k-set agreement problem in a synchronous system. it considers that the system is enriched with base objects (denoted has [m,@?]_sa objects) that allow solving the @?-set agreement problem in a set of m processes (m
on the complexities of consistency checking for restricted uml class diagrams. automatic debugging of uml class diagrams helps in the visual specification of software systems because users cannot detect errors in logical consistency easily. this study focuses on the tractable consistency checking of uml class diagrams. we accurately identify inconsistencies in these diagrams by translating them into first-order predicate logic that is generalized by counting quantifiers and classify their expressivities by eliminating certain components. we introduce optimized algorithms that compute the respective consistencies of class diagrams of different expressive powers in p, np, pspace, or exptime with respect to the size of the class diagrams. in particular, owing to the restrictions imposed on attribute value types, the complexities of consistency checking of class diagrams decrease from exptime to p and pspace in two cases: (i) when the class diagrams contain disjointness constraints and overwriting/multiple inheritances and (ii) when the class diagrams contain both these components along with completeness constraints. additionally, we confirm the existence of a restriction of class diagrams that prevents any logical inconsistency.
maximal width learning of binary functions. this paper concerns learning binary-valued functions defined on r, and investigates how a particular type of 'regularity' of hypotheses can be used to obtain better generalization error bounds. we derive error bounds that depend on the sample width (a notion analogous to that of sample margin for real-valued functions). this motivates learning algorithms that seek to maximize sample width.
on-demand strategy annotations revisited: an improved on-demand evaluation strategy. in functional languages such as obj*, cafeobj, and maude, symbols are given strategy annotations that specify (the order in) which subterms are evaluated. syntactically, strategy annotations are given either as lists of natural numbers or as lists of integers associated to function symbols whose (absolute) values refer to the arguments of the corresponding symbol. a positive index prescribes the evaluation of an argument whereas a negative index means ''evaluation on-demand''. these on-demand indices have been proposed to support laziness in obj-like languages. while strategy annotations containing only natural numbers have been implemented and investigated to some extent (regarding, for example, termination, confluence, and completeness), fully general annotations (including positive and negative indices) have been disappointingly under-explored to date. in this paper, we first point out a number of problems of current proposals for handling on-demand strategy annotations. then, we propose a solution to these problems by keeping an accurate track of annotations along the evaluation sequences. we formalize this solution as a suitable extension of the evaluation strategy of obj-like languages (which only consider annotations given as natural numbers) to on-demand strategy annotations. our on-demand evaluation strategy (ode) overcomes the drawbacks of previous proposals and also has better computational properties. for instance, we show how to use this strategy for computing (head-)normal forms. we also introduce a transformation which allows us to prove the termination of the new evaluation strategy by using standard rewriting techniques. finally, we present two interpreters of the new strategy together with some encouraging experiments which demonstrate the usefulness of our approach.
np-hard and linear variants of hypergraph partitioning. this article presents an infinite family of combinatorial problems that shows abrupt changes of complexity between neighbour problems. we define problem p"k^l as a purely constraint-driven variant of hypergraph partitioning with parameters k and l as follows. given a hypergraph on n vertices and k sizes of colours t"1,...,t"k of sum n, can we colour the vertices with k colours of given size such that each hyperedge intersects at most l colours? we show that, for fixed parameters k and l, p"k^l is: polynomial when l=1, and np-complete when l1 on the class of hypergraphs with pairwise disjoint hyperedges. this inversion of complexity is possible since hypergraphs with disjoint hyperedges can be encoded in a more compact way, namely @q(mlog(n)) instead of @q(mn) bits (n and m are the number of vertices and edges of the hypergraph).
canonical finite state machines for distributed systems. there has been much interest in testing from finite state machines (fsms) as a result of their suitability for modelling or specifying state-based systems. where there are multiple ports/interfaces a multi-port fsm is used and in testing, a tester is placed at each port. if the testers cannot communicate with one another directly and there is no global clock then we are testing in the distributed test architecture. it is known that the use of the distributed test architecture can affect the power of testing and recent work has characterised this in terms of local s-equivalence: in the distributed test architecture we can distinguish two fsms, such as an implementation and a specification, if and only if they are not locally s-equivalent. however, there may be many fsms that are locally s-equivalent to a given fsm and the nature of these fsms has not been explored. this paper examines the set of fsms that are locally s-equivalent to a given fsm m. it shows that there is a unique smallest fsm @g"m"i"n(m) and a unique largest fsm @g"m"a"x(m) that are locally s-equivalent to m. here smallest and largest refer to the set of traces defined by an fsm and thus to its semantics. we also show that for a given fsm m the set of fsms that are locally s-equivalent to m defines a bounded lattice. finally, we define an fsm that, amongst all fsms locally s-equivalent to m, has fewest states. we thus give three alternative canonical fsms that are locally s-equivalent to an fsm m: one that defines the smallest set of traces, one that defines the largest set of traces, and one with fewest states. all three provide valuable information and the first two can be produced in time that is polynomial in terms of the number of states of m. we prove that the problem of finding an s-equivalent fsm with fewest states is np-hard in general but can be solved in polynomial time for the special case where there are two ports.
mechanism design for set cover games with selfish element agents. in this article, we study the set cover games when the elements are selfish agents, each of which has a privately known valuation of receiving the service from the sets, i.e., being covered by some set. each set is assumed to have a fixed cost. we develop several approximately efficient strategyproof mechanisms that decide, after soliciting the declared bids by all elements, which elements will be covered, which sets will provide the coverage to these selected elements, and how much each element will be charged. for single-cover set cover games, we present a mechanism that is at least 1d"m"a"x-efficient, i.e., the total valuation of all selected elements is at least 1d"m"a"x fraction of the total valuation produced by any mechanism. here, d"m"a"x is the maximum size of the sets. for multi-cover set cover games, we present a budget-balanced strategyproof mechanism that is 1d"m"a"xh"d"""m"""a"""x-efficient under reasonable assumptions. here, h"n is the harmonic function. for the set cover games when both sets and elements are selfish agents, we show that a cross-monotonic payment-sharing scheme does not necessarily induce a strategyproof mechanism.
maximum likelihood analysis of algorithms and data structures. we present a new approach for an average-case analysis of algorithms and data structures that supports a non-uniform distribution of the inputs and is based on the maximum likelihood training of stochastic grammars. the approach is exemplified by an analysis of the expected size of binary tries as well as by three sorting algorithms and it is compared to the known results that were obtained by traditional techniques. investigating traditional settings like the random permutation model, we rediscover well-known results formerly derived by pure analytic methods; changing to biased data yields original results. all but one step of our analysis can be automated on top of a computer-algebra system. thus our new approach can reduce the effort required for an average-case analysis, allowing for the consideration of realistic input distributions with unknown distribution functions at the same time. as a by-product, our approach yields an easy way to generate random combinatorial objects according to various probability distributions.