waashk/dblp huggingface dataset:
lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling. the authors prove a lower bound of omega (log n/log log n) on the competitive ratio of any (deterministic or randomised) distributed algorithm for solving the mobile user problem on certain networks of n processors. the lower bound holds for various networks, including the hypercube, any network with sufficiently large girth, and any highly expanding graph. a similar omega (log n/log log n) lower bound is proved for the competitive ratio of the maximum job delay of any distributed algorithm for solving a distributed scheduling problem on any of these networks. the proofs combine combinatorial techniques with tools from linear algebra and harmonic analysis and apply, in particular, a generalization of the vertex isoperimetric problem on the hypercube, which may be of independent interest.
a new algorithm for regularizing one-letter context-free grammars. constructive methods for obtaining regular grammar counterparts for some sub-classes of context-free grammars (cfgs) have been investigated by many researchers. an important class of grammars for which this is always possible is the one-letter cfg. we show in this paper a new constructive method for transforming an arbitrary one-letter cfg to an equivalent regular expression of star-height 0 or 1. our new result is considerably simpler than a previous construction by leiss, and we also propose a new normal form for a regular expression with only a single-star occurrence. through an alphabet factorization theorem, we show how to go beyond the one-letter cfg in a straight-forward way.
rules + strategies for transforming lazy functional logic programs. this work introduces a transformation methodology for functional logic programs based on needed narrowing, the optimal and complete operational principle for modern declarative languages which integrate the best features of functional and logic programming. we provide correctness results for the transformation system w.r.t, the set of computed values and answer substitutions and show that the prominent properties of needed narrowing--namely, the optimality w.r.t, the length of derivations and the number of computed solutions--carry over to the transformation process and the transformed programs. we illustrate the power of the system by taking on in our setting two well-known transformation strategies (composition and tupling). we also provide an implementation of the transformation system which, by means of some experimental results, highlights the potentiality of our approach.
deeper model endgame analysis. a reference model of fallible endgame play has been implemented and exercised with the chess-engine wilhelm. past experiments have demonstrated the value of the model and the robustness of decisions based on it: experiments agree well with a markov model theory. here, the reference model is exercised on the well-known endgame kbbkn.
a semantic framework for the abstract model checking of tccp programs. the timed concurrent constraint programming language (tccp) introduces time aspects into the concurrent constraint paradigm. this makes tccp especially appropriate for analyzing timing properties of concurrent systems by model checking. however, even if very compact state representations are obtained thanks to the use of constraints in tccp, large state spaces can still be generated, which may prevent model-checking tools from verifying tccp programs completely. model checking tccp programs is a difficult task due to the subtleties of the underlying operational semantics, which combines constraints, concurrency, non-determinism and time. currently, there is no practical model-checking tool that is applicable to tccp. in this work, we introduce an abstract methodology which is based on over-and under-approximating tccp models and which mitigates the state explosion problem that is common to traditional model-checking algorithms. we ascertain the conditions for the correctness of the abstract technique and show that this preliminary abstract semantics does not correctly simulate the suspension behavior, which is a key feature of tccp. then, we present a refined abstract semantics which correctly models suspension. finally, we complete our methodology by approximating the temporal properties that must be verified.
approximating the pareto curve with local search for the bicriteria tsp(1, 2) problem. local search has been widely used in combinatorial optimization (local search in combinatorial optimization, wiley, new york, 1997), however, in the case of multicriteria optimization almost no results are known concerning the ability of local search algorithms to generate "good" solutions with performance guarantee. in this paper, we introduce such an approach for the classical traveling salesman problem (tsp) problem (proc. stoc'00, 2000, pp. 126-133). we show that it is possible to get in linear time, a 3/2-approximate pareto curve using an original local search procedure based on the 2-opt neighborhood, for the bicriteria tsp(1,2) problem where every edge is associated to a couple of distances which are either 1 or 2 (math. oper. res. 18 (1) (1993) 1).
improved game play by multiple computer hint. humans and computers have different strengths, which should be combined, not wasted. multiple-choice systems are an efficient way to achieve this goal. an instructive example is 3-hirn, where two programs make one proposal each and a human boss has the final choice amongst them. in chess and several other brain games many experiments with 3-hirn and other settings proved the usefulness of multiple choice systems and the validity of the underlying ideas.
on the approximate tradeoff for bicriteria batching and parallel machine scheduling problems. we consider multiobjective scheduling problems, i.e. scheduling problems that are evaluated with respect to many cost criteria, and we are interested in determining a trade-off (pareto curve) among these criteria. we study two types of bicriteria scheduling problems: single-machine batching problems and parallel machine scheduling problems. instead of proceeding in a problem-by-problem basis, we identify a class of multiobjective optimization problems possessing a fully polynomial time approximation scheme (fptas) for computing an ε-approximate pareto curve. this class contains a set of problems whose pareto curve can be computed via a simple pseudo-polynomial dynamic program for which the objective and transition functions satisfy some, easy to verify, arithmetical conditions. our study is based on a recent work of woeginger (electronic colloquium on computational complexity, report 84 (short version appeared in soda'99, pp. 820-829)) for the single criteria optimization ex-benevolent problems. we show how our general result can be applied to the considered scheduling problems.
on the landscape ruggedness of the quadratic assignment problem. local-search-based heuristics have been demonstrated to give very good results to approximately solve the quadratic assignment problem (qap). in this paper, following the works of weinberger and stadler, we introduce a parameter, called the ruggedness coeffcient, which measures the ruggedness of the qap landscape which is the union of a cost function and a neighborhood. we give an exact expression, and a sharp lower bound for this parameter. we are able toderive from it that the landscape of the qap is rather flat, and so it gives a theoretical justification of the effectiveness of local-search-based heuristics for this problem. experimental results with simulated annealing are presented which con8rm this conclusion and also the influence of the ruggedness coe5cient on the quality of results obtained.
solution of a problem in dna computing. we answer a question of rozenberg and salomaa arising from a problem in dna computing. this problem was posed at the icalp conference in july 1999 in prague.
the algorithmic analysis of hybrid systems. we present a general framework for the formal specification and algorithmic analysis of hybrid systems. a hybrid system consists of a discrete program with an analog environment. we model hybrid systems as finite automata equipped with variables that evolve continuously with time according to dynamical laws. for verification purposes, we restrict ourselves to linear hybrid systems, where all variables follow piecewise-linear trajectories. we provide decidability and undecidability results for classes of linear hybrid systems, and we show that standard program-analysis techniques can be adapted to linear hybrid systems. in particular, we consider symbolic model-checking and minimization procedures that are based on the reachability analysis of an infinite state space. the procedures iteratively compute state sets that are definable as unions of convex polyhedra in multidimensional real space. we also present approximation techniques for dealing with systems for which the iterative procedures do not converge.
on the complexity of inducing categorical and quantitative association rules. inducing association rules is one of the central tasks in data mining applications. quantitative association rules induced from databases describe rich and hidden relationships to be found within data that can prove useful for various application purposes (e.g., market basket analysis, customer profiling, and others). although association rules are quite widely used in practice, a thorough analysis of the related computational complexity is missing. this paper intends to provide a contribution in this setting. to this end, we first formally define quantitative association rule mining problems, which include boolean association rules as a special case; we then analyze computational complexity of such problems. the general problem as well as some interesting special cases are considered.
counterexample-guided predicate abstraction of hybrid systems. predicate abstraction has emerged to be a powerful technique for extracting finite-state models from infinite-state systems, and has been recently shown to enhance the effectiveness of the teachability computation techniques for hybrid systems. given a hybrid system with linear dynamics and a set of linear predicates, the verifier performs an on-the-fly search of the finite discrete quotient whose states correspond to the truth assignments to the input predicates. the success of this approach depends on the choice of the predicates used for abstraction. in this paper, we focus on identifying these predicates automatically by analyzing spurious counterexamples generated by the search in the abstract state-space. we present the basic techniques for discovering new predicates that will rule out closely related spurious counterexamples, optimizations of these techniques, implementation of these in the verification tool, and case studies demonstrating the promise of the approach.
queries revisited. we begin with a brief tutorial on the problem of learning a finite concept class over a finite domain using membership queries and/or equivalence queries. we then sketch general results on the number of queries needed to learn a class of concepts, focusing on the various notions of combinatorial dimension that have been employed, including the teaching dimension, the exclusion dimension, the extended teaching dimension, the fingerprint dimension, the sample exclusion dimension, the vapnik-chervonenkis dimension, the abstract identification dimension, and the general dimension.
realizability and verification of msc graphs. scenario-based specifications such as message sequence charts (msc) offer an intuitive and visual way to describe design requirements. msc-graphs allow convenient expression of multiple scenarios, and can be viewed as an early model of the system that can be subjected to a variety of analyses. problems such as ltl model checking are undecidable for msc-graphs in general, but are known to be decidable for the class of bounded msc-graphs.our first set of results concerns checking realizability of bounded msc-graphs. an msc-graph is realizable if there is a distributed implementation that generates precisely the behaviors in the graph. there are two notions of realizability, weak and safe, depending on whether or not we require the implementation to be deadlock-free. it is known that for a finite set of mscs, weak realizability is conp-complete while safe realizability has a polynomial-time solution. we establish that for bounded msc-graphs, weak realizability is, surprisingly, undecidable, while safe realizability is in expspace.our second set of results concerns verification of msc-graphs. while checking properties of a graph g, besides verifying all the scenarios in the set l(g) of mscs specified by g, it is desirable to verify all the scenarios in the set lw(g)--the closure of g, that contains the implied scenarios that any distributed implementation of g must include. for checking whether a given msc m is a possible behavior, checking m ∈ l(g) is np-complete, but checking m ∈ lw(g) has a quadratic solution. for temporal logic specifications, considering the closure makes the verification problem harder: while checking ltl properties of l(g) is pspace-complete for bounded graphs g, checking even simple "local" properties of lw(g) is undecidable.
modular strategies for recursive game graphs. many problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. in this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. while such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. while reachability in (global) pushdown games is known to be exptime-complete, we show reachability in modular games to be np-complete. we present a fixed-point computation algorithm for solving modular games such that in the worst case the number of iterations is exponential in the total number of returned values from the modules. if the strategy within a module does not depend on the global history, but can remember the history of the past invocations of this module, that is, if memory is local but persistent, we show that reachability becomes undecidable.
neural learning methods yielding functional invariance. this paper investigates the functional invariance of neural network learning methods incorporating a complexity reduction mechanism, such as a regularizer. by functional invariance we mean the property of producing functionally equivalent minima as the size of the network grows, when the smoothing parameters are fixed. we study three different principles on which functional invariance can be based, and try to delimit the conditions under which each of them acts. we find out that, surprisingly, some of the most popular neural learning methods, such as weight-decay and input noise addition, exhibit this interesting property.
optimal paths in weighted timed automata. we consider the optimal-reachability problem for a timed automaton with respect to a linear cost function which results in a weighted timed automaton. our solution to this optimization problem consists of reducing it to computing (parametric) shortest paths in a finite weighted directed graph. we call this graph a parametric sub-region graph. it refines the region graph, a standard tool for the analysis of timed automata, by adding the information which is relevant to solving the optimal-teachability problem. we present an algorithm to solve the optimal-reachability problem for weighted timed automata that takes time exponential in o(<i>n</i>(|δ(<i>a</i>)| + |<i>w</i><inf>max</inf>|)), where <i>n</i> is the number of clocks, |δ(<i>a</i>)| is the size of the clock constraints and |<i>w</i><inf>max</inf>| is the size of the largest weight. we show that this algorithm can be improved, if we restrict to weighted timed automata with a single clock. in case we consider a single starting state for the optimal-reachability problem, our approach yields an algorithm that takes exponential time only in the length of clock constraints.
broadcasting in unstructured peer-to-peer overlay networks. peer-to-peer overlay networks present new opportunities and challenges for achieving enhanced network functionality at the application level. in this paper we study the impact of point-to-point network latency on flooding broadcast operations in peer-to-peer overlay networks. we show that two standard protocol mechanisms, used to control the amount of network resources used during flooding, can in combination, significantly reduce the reach of broadcast messages. we prove that these standard mechanisms, known as "time-to-live bounds" and "unique message identification", can result in broadcast operations that only reach a vanishing fraction of the nodes. in addition, we provide empirical evidence that the trend suggested by our formal results are found in data obtained from the gnutefla network and through network simulations.
weak linearization of the lambda calculus. we identify a restricted class of terms of the lambda calculus, here called weak linear, that includes the linear lambda-terms keeping their good properties of strong normalization, non-duplicating reductions and typability in polynomial time. the advantage of this class over the linear lambda-calculus is the possibility of transforming general terms into weak linear terms with the same normal form. we present such transformation and prove its correctness by showing that it preserves normal forms.
on the symbolic reduction of processes with cryptographic functions. we study the reachability problem for cryptographic protocols represented as processes relying on perfect cryptographic functions. we introduce a symbolic reduction system that can handle hashing functions, symmetric keys, and public keys. desirable properties such as secrecy or authenticity are specified by inserting logical assertions in the processes.we show that the symbolic reduction system provides a flexible decision procedure for finite processes and a reference for sound implementations. the symbolic reduction system can be regarded as a variant of syntactic unification which is compatible with certain set-membership constraints. for a significant fragment of our formalism, we argue that a dag implementation of the symbolic reduction system leads to an algorithm running in nptime thus matching the lower bound of the problem.in the case of iterated or finite control processes, we show that the problem is undecidable in general and in ptime for a subclass of iterated processes that do not rely on pairing. our technique is based on rational transductions of regular languages and it applies to a class of processes containing the ping-pong protocols presented in dolev et al. (inform. comput. (55) (1982) 57).
new operations and regular expressions for two-dimensional languages over one-letter alphabet. we consider the problem of defining regular expressions to characterize the class of recognizable picture languages in the case of a one-letter alphabet. we define a diagonal concatenation and its star and consider two different families, l(d) and l(crd), of languages denoted by regular expressions involving such operations plus classical operations. l(d) is characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. l(crd) is included in rec and contains languages defined by three-way automata while languages in l(crd) necessarily satisfy some regularity conditions. finally, we introduce new definitions of advanced stars expressing the necessity of conceptually different definitions for iteration.
on learning monotone boolean functions under the uniform distribution. in this paper, we prove two general theorems on monotone boolean functions which are useful for constructing a learning algorithm for monotone boolean functions under the uniform distribution.a monotone boolean function is called fair if it takes the value 1 on exactly half of its inputs. the first result proved in this paper is that a single variable function f(x) = xi has the minimum correlation with the majority function among all fair monotone functions. this proves the conjecture by blum et al. (1998, proc. 39th focs, pp. 408-415) and improves the performance guarantee of the best known learning algorithm for monotone boolean functions under the uniform distribution they proposed.our second result is on the relationship between the influences and the average sensitivity of a monotone boolean function. the influence of variable xi on f is defined as the probability that f(x) differs from f(x ⊕ ei) where x is chosen uniformly from {0, 1}n and x ⊕ ei means x with its ith bit flipped. the average sensitivity of f is defined as the sum of the influences over all variables xi. we prove that a somewhat unintuitive result which says if the influence of every variable on a monotone boolean function is small, i.e., o(1/nc) for some constant c > 0, then the average sensitivity of the function must be large, i.e., ω(log n). we also discuss how to apply this result to the construction of a new learning algorithm for monotone boolean functions.
taming the complexity of biochemical models through bisimulation and collapsing: theory and practice. many biological systems can be modeled using systems of ordinary differential algebraic equations (e.g., s-systems), thus allowing the study of their solutions and behavior automatically with suitable software tools (e.g., plas, octave/matlabtm). usually, numerical solutions (traces or trajectories) for appropriate initial conditions are analyzed in order to infer significant properties of the biological systems under study. when several variables are involved and the traces span over a long interval of time, the analysis phase necessitates automation in a scalable and efficient manner. earlier, we have advocated and experimented with the use of automata and temporal logics for this purpose (xs-systems and simpathica) and here we continue our investigation more deeply.we propose the use of hybrid automata and we discuss the use of the notions of bisimulation and collapsing for a "qualitative" analysis of the temporal evolution of biological systems. as compared with our previous approach, hybrid automata allow maintenance of more information about the differential equations (s-system) than standard automata. the use of the notion of bisimulation in the definition of the projection operation (restrictions to a subset of "interesting" variables) makes it possible to work with reduced automata satisfying the same formulae as the initial ones. finally, the notion of collapsing is introduced to move toward still simpler and equivalent automaton taming the complexity in terms of states whose number depends on the attained level of approximation.
lower bounds for the rate of convergence in nonparametric pattern recognition. we show that there exist individual lower bounds corresponding to the upper bounds for the rate of convergence of nonparametric pattern recognition which are arbitrarily close to yang's minimax lower bounds, for certain "cubic" classes of regression functions used by stone and others. the rates are equal to the ones of the corresponding regression function estimation problem. thus for these classes classification is not easier than regression function estimation.