waashk/dblp huggingface dataset:
covering by squares. in this paper we introduce the ''do not touch'' condition for squares in the discrete plane. we say that two squares ''do not touch'' if they do not share any vertex or any segment of an edge. using this condition we define a covering of the discrete plane, the covering can be strong or weak, regular or non-regular. for simplicity, in this article, we will restrict our attention to regular coverings, i.e., only a size is allowed for the squares and all the squares have the same number of adjacent squares. we establish minimal conditions for the existence of a weak or strong regular covering of the discrete plane, and we give a bound for the number of adjacent squares with respect to the size of the squares in the regular covering.
a better differential approximation ratio for symmetric tsp. in this paper, we study the approximability properties of symmetric tsp under an approximation measure called the differential ratio. more precisely, we improve up to 3/4-@e (for any @e>0) the best differential ratio of 2/3 known so far, given in hassin and khuller, [r. hassin, s. khuller, z-approximations, j. algorithms, 41 (2) (2001) 429-442].
inverse min-max spanning tree problem under the weighted sum-type hamming distance. the inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. in this paper, we consider the inverse min-max spanning tree problem under the weighted sum-type hamming distance. for the model considered, we present its combinatorial algorithm that runs in strongly polynomial times.
world-set decompositions: expressiveness and efficient algorithms. uncertain information is commonplace in real-world data management scenarios. the ability to represent large sets of possible instances (worlds) while supporting efficient storage and processing is an important challenge in this context. the recent formalism of world-set decompositions (wsds) provides a space-efficient representation for uncertain data that also supports scalable processing. wsds are complete for finite world-sets in that they can represent any finite set of possible worlds. for possibly infinite world-sets, we show that a natural generalization of wsds precisely captures the expressive power of c-tables. we then show that several important problems are efficiently solvable on wsds while they are np-hard on c-tables. finally, we give a polynomial-time algorithm for factorizing wsds, i.e. an efficient algorithm for minimizing such representations.
competitive analysis of most-request-first for scheduling broadcasts with start-up delay. in this paper, we give a tight and complete mathematical analysis of the most-request-first algorithm for scheduling on-demand broadcasts with start-up delay. the algorithm is natural and simple, yet its practical performance is surprisingly good. we derive tight upper and lower bounds on its competitive ratio under different system configurations. our results reveal an interesting relationship between the start-up delay and the competitiveness of the algorithm.
combinatorial gray codes for classes of pattern avoiding permutations. the past decade has seen a flurry of research into pattern avoiding permutations but little of it is concerned with their exhaustive generation. many applications call for exhaustive generation of permutations subject to various constraints or imposing a particular generating order. in this paper we present generating algorithms and combinatorial gray codes for several families of pattern avoiding permutations. among the families under consideration are those counted by catalan, large schroder, pell, even-index fibonacci numbers and the central binomial coefficients. we thus provide gray codes for the set of all permutations of {1,...,n} avoiding the pattern @t for all @t@?s"3 and the gray codes we obtain have distances 4 or 5.
non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. this paper presents a distributed algorithm whereby a group of mobile robots self-organize and position themselves into forming a circle in a loosely synchronized environment. in spite of its apparent simplicity, the difficulty of the problem comes from the weak assumptions made on the system. in particular, robots are anonymous, oblivious (i.e., stateless), unable to communicate directly, and disoriented in the sense that they share no knowledge of a common coordinate system. furthermore, robots' activations are not synchronized. more specifically, the proposed algorithm ensures that robots deterministically form a non-uniform circle in a finite number of steps and converges to a situation in which all robots are located evenly on the boundary of the circle.
modelling the navigation potential of a web page. navigating the web involves pruning (or discounting) some of the outgoing links and following one of the others. more pruning is likely to happen for deeper navigation. under this model of navigation, we call the number of nodes that are available after pruning, for browsing within a session, the potential gain of the starting web page. we first consider the case when the discounting factor is geometric. we show that the distribution of the effective number of links that the user can follow at each navigation step after pruning, i.e. the number of nodes added to the potential gain at that step, is given by the erf function, which is related to the probability density function for the normal distribution. we derive an approximation to the potential gain of a web page and show numerically that it is very accurate; we also obtain lower and upper bounds. we then consider a harmonic discounting factor and show that, in this case, the potential gain at each step is closely related to the probability density function for the poisson distribution. the potential gain has been applied to web navigation where, given no other information, it helps the user to choose a good starting point for initiating a ''surfing'' session. another application is in social network analysis, where the potential gain could provide a novel measure of centrality.
jug measuring: algorithms and complexity. we study the hardness of the optimal jug measuring problem. by proving tight lower and upper bounds on the minimum number of measuring steps required, we reduce an inapproximable np-hard problem (i.e., the shortest gcd multiplier problem [g. havas, j.-p. seifert, the complexity of the extended gcd problem, in: lncs, vol. 1672, springer, 1999]) to it. it follows that the optimal jug measuring problem is np-hard and so is the problem of approximating the minimum number of measuring steps within a constant factor. along the way, we give a polynomial-time approximation algorithm with an exponential error based on the well-known lll basis reduction algorithm.
an improved lower bound for approximating minimum gcd multiplier in l norm (gcdm). in this paper, we study the inapproximability of the following np-complete number theoretic optimization problems introduced by rossner and seifert [c. rossner, j.p. seifert, the complexity of approximate optima for greatest common divisor computations, in: proceedings of the 2nd international algorithmic number theory symposium, ants-ii, 1996, pp. 307-322]: given n numbers a"1,...,a"n@?z, find an @?"~-minimum gcd multiplier for a"1,...,a"n, i.e., a vector x@?z^n with minimum max"1"@?"i"@?"n|x"i| satisfying @?"i"="1^nx"ia"i=gcd(a"1,...,a"n). we show that assuming p0 where n is the dimension of the given vector. this improves on the best previous result. the best result so far gave 2^(^l^o^g^n^)^^^1^^^-^^^@e factor hardness by rossner and seifert [c. rossner, j.p. seifert, the complexity of approximate optima for greatest common divisor computations, in: proceedings of the 2nd international algorithmic number theory symposium, ants-ii, 1996, pp. 307-322], where @e>0 is an arbitrarily small constant.
the complexity of deciding reachability properties of distributed negotiation schemes. distributed negotiation schemes offer one approach to agreeing an allocation of resources among a set of individual agents. such schemes attempt to agree a distribution via a sequence of locally agreed 'deals'-reallocations of resources among the agents-ending when the result satisfies some accepted criteria. our aim in this article is to demonstrate that some natural decision questions arising in such settings can be computationally significantly harder than questions related to optimal clearing strategies in combinatorial auctions. in particular we prove that the problem of deciding whether it is possible to progress from a given initial allocation to some desired final allocation via a sequence of ''rational'' steps is pspace-complete.
measuring teachability using variants of the teaching dimension. in a typical algorithmic learning model, a learner has to identify a target object from partial information. conversely, in a teaching model a teacher has to give information that allows the learners to identify a target object. we devise two variants of the classical teaching model for boolean concept classes, based on the teaching dimension, and describe them by teaching-dimension-like combinatorial parameters. in the first model, the learners choose consistent hypotheses with least complexity. we show that 1-decision lists are the harder to teach the longer they are and that 2-term dnfs are the harder to teach the more terms they have. this contrasts with the teachability results for these classes in the teaching-dimension model. in our second model, the learners choose consistent hypotheses based on the assumption that the teacher is optimal. we show that monomials can be taught with a linear number of examples, whereas some 1-decision lists need exponentially many.
developments from enquiries into the learnability of the pattern languages from positive data. the pattern languages are languages that are generated from patterns, and were first proposed by angluin as a non-trivial class that is inferable from positive data [d. angluin, finding patterns common to a set of strings, journal of computer and system sciences 21 (1980) 46-62; d. angluin, inductive inference of formal languages from positive data, information and control 45 (1980) 117-135]. in this paper we chronologize some results that developed from the investigations on the inferability of the pattern languages from positive data.
reflective inductive inference of recursive functions. in this paper, we investigate reflective inductive inference of recursive functions. a reflective iim is a learning machine that is additionally able to assess its own competence. first, we formalize reflective learning from arbitrary, and from canonical, example sequences. here, we arrive at four different types of reflection: reflection in the limit, optimistic, pessimistic and exact reflection. then, we compare the learning power of reflective iims with each other as well as with the one of standard iims for learning in the limit, for consistent learning of three different types, and for finite learning.
some classes of term rewriting systems inferable from positive data. in this paper, we study the inferability of term rewriting systems (trss, for short) from positive examples alone. two classes of trss inferable from positive data are presented, namely, simple flat trss and linear-bounded trss. these classes of trss are rich enough to include many divide-and-conquer programs like addition, doubling, logarithm, tree-count, list-count, split, append, reverse, etc. the classes of simple flat trss and linear-bounded trss are incomparable, i.e., there are functions that can be computed by simple flat trss but not by linear-bounded trss and vice versa.
learning and extending sublanguages. a number of natural models for learning in the limit are introduced to deal with the situation when a learner is required to provide a grammar covering the input even if only a part of the target language is available. examples of language families are exhibited that are learnable in one model and not learnable in another one. some characterizations for learnability of algorithmically enumerable families of languages for the models in question are obtained. since learnability of any part of the target language does not imply monotonicity of the learning process, we consider our models also under the additional monotonicity constraint.
quantum inductive inference by finite automata. freivalds and smith [r. freivalds, c.h. smith memory limited inductive inference machines, springer lecture notes in computer science 621 (1992) 19-29] proved that probabilistic limited memory inductive inference machines can learn with probability 1 certain classes of total recursive functions, which cannot be learned by deterministic limited memory inductive inference machines. we introduce quantum limited memory inductive inference machines as quantum finite automata acting as inductive inference machines. these machines, we show, can learn classes of total recursive functions not learnable by any deterministic, nor even by probabilistic, limited memory inductive inference machines.
learning indexed families of recursive languages from positive data: a survey. in the past 40 years, research on inductive inference has developed along different lines, e.g., in the formalizations used, and in the classes of target concepts considered. one common root of many of these formalizations is gold's model of identification in the limit. this model has been studied for learning recursive functions, recursively enumerable languages, and recursive languages, reflecting different aspects of machine learning, artificial intelligence, complexity theory, and recursion theory. one line of research focuses on indexed families of recursive languages - classes of recursive languages described in a representation scheme for which the question of membership for any string in any of the given languages is effectively decidable with a uniform procedure. such language classes are of interest because of their naturalness. the survey at hand picks out important studies on learning indexed families (including basic as well as recent research), summarizes and illustrates the corresponding results, and points out links to related fields such as grammatical inference, machine learning, and artificial intelligence in general.
learning recursive functions: a survey. studying the learnability of classes of recursive functions has attracted considerable interest for at least four decades. starting with gold's (1967) model of learning in the limit, many variations, modifications and extensions have been proposed. these models differ in some of the following: the mode of convergence, the requirements intermediate hypotheses have to fulfill, the set of allowed learning strategies, the source of information available to the learner during the learning process, the set of admissible hypothesis spaces, and the learning goals. a considerable amount of work done in this field has been devoted to the characterization of function classes that can be learned in a given model, the influence of natural, intuitive postulates on the resulting learning power, the incorporation of randomness into the learning process, the complexity of learning, among others. on the occasion of rolf wiehagen's 60th birthday, the last four decades of research in that area are surveyed, with a special focus on rolf wiehagen's work, which has made him one of the most influential scientists in the theory of learning recursive functions.
discontinuities in pattern inference. this paper deals with the inferrability of classes of e-pattern languages-also referred to as extended or erasing pattern languages-from positive data in gold's model of identification in the limit. the first main part of the paper shows that the recently presented negative result on terminal-free e-pattern languages over binary alphabets does not hold for other alphabet sizes, so that the full class of these languages is inferrable from positive data if and only if the corresponding terminal alphabet does not consist of exactly two distinct letters. the second main part yields the insight that the positive result on terminal-free e-pattern languages over alphabets with three or four letters cannot be extended to the class of general e-pattern languages. with regard to larger alphabets, the extensibility remains open. the proof methods developed for these main results do not directly discuss the (non-)existence of appropriate learning strategies, but they deal with structural properties of classes of e-pattern languages, and, in particular, with the problem of finding telltales for these languages. it is shown that the inferrability of classes of e-pattern languages is closely connected to some problems on the ambiguity of morphisms so that the technical contributions of the paper largely consist of combinatorial insights into morphisms in word monoids.
nonstochastic bandits: countable decision set, unbounded costs and reactive environments. the nonstochastic multi-armed bandit problem, first studied by auer, cesa-bianchi, freund, and schapire in 1995, is a game of repeatedly choosing one decision from a set of decisions (''experts''), under partial observation: in each round t, only the cost of the decision played is observable. a regret minimization algorithm plays this game while achieving sublinear regret relative to each decision. it is known that an adversary controlling the costs of the decisions can force the player a regret growing as t^1^2 in the time t. in this work, we propose the first algorithm for a countably infinite set of decisions, that achieves a regret upper bounded by o(t^1^2^+^@e), i.e. arbitrarily close to optimal order. to this aim, we build on the ''follow the perturbed leader'' principle, which dates back to work by hannan in 1957. our results hold against an adaptive adversary, for both the expected and high probability regret of the learner w.r.t. each decision. in the second part of the paper, we consider reactive problem settings, that is, situations where the learner's decisions impact on the future behaviour of the adversary, and a strong strategy can draw benefit from well chosen past actions. we present a variant of our regret minimization algorithm which has still regret of order at most t^1^2^+^@e relative to such strong strategies, and even sublinear regret not exceeding o(t^4^5) w.r.t. the hypothetical (without external interference) performance of a strong strategy. we show how to combine the regret minimizer with a universal class of experts, given by the countable set of programs on some fixed universal turing machine. this defines a universal learner with sublinear regret relative to any computable strategy.
absolute versus probabilistic classification in a logical setting. suppose we are given a set w of logical structures, or possible worlds, a set of logical formulas called possible data and a logical formula @f. we then consider the classification problem of determining in the limit and almost always correctly whether a possible world m satisfies @f, from a complete enumeration of the possible data that are true in m. one interpretation of almost always correctly is that the classification might be wrong on a set of possible worlds of measure 0, with respect to some natural probability distribution over the set of possible worlds. another interpretation is that the classifier is only required to classify a set w^' of possible worlds of measure 1, without having to produce any claim in the limit on the truth of @f for the members of the complement of w^' in w. we compare these notions with absolute classification of w with respect to a formula that is almost always equivalent to @f in w, hence we investigate whether the set of possible worlds on which the classification is correct is definable. we mainly work with the probability distribution that corresponds to the standard measure on the cantor space, but we also consider an alternative probability distribution proposed by solomonoff and contrast it with the former. finally, in the spirit of the kind of computations considered in logic programming, we address the issue of computing almost correctly in the limit witnesses to leading existentially quantified variables in existential formulas.
access control in mobile ambient calculi: a comparative view. ambient calculi represent a class of process calculi used to describe and model mobile and distributed computations. this paper examines the most relevant of these calculi and focuses on an important dimension: the access control problem. in the security world, a system is considered trusted if it controls the access to its resources, i.e. every request for the access to a resource is honored if and only if the subject requiring the resource is an authorized user of the system and the request agrees with a given policy. so the security problem for ambient calculi is investigated considering the authentication mechanism and the possibility to implement security policies. two examples have been chosen to illustrate these topics: the firewall and the communication by means of named channels.
a type assignment system for game semantics. we present a type assignment system that provides a finitary interpretation of lambda terms in a game semantics model. traditionally, type assignment systems describe the semantic interpretation of terms in domain-theoretic models. quite surprisingly, the type assignment system presented in this paper is very similar to the traditional ones, the main difference being the omission of the subtyping rules.
semantic subtyping for the pi-calculus. subtyping relations for the @p-calculus are usually defined in a syntactic way, by means of structural rules. we propose a semantic characterisation of channel types and use it to derive a subtyping relation. the type system we consider includes read-only and write-only channel types, as well as boolean combinations of types. a set-theoretic interpretation of types is provided, in which boolean combinations of types are interpreted as the corresponding set-theoretic operations. subtyping is defined as inclusion of the interpretations. we prove decidability of the subtyping relation and sketch the subtyping algorithm. in order to fully exploit the type system, we define a variant of the @p-calculus where communication is subjected to pattern matching that performs dynamic typecase.
extending feathertrait java with interfaces. in the context of featherweight java by igarashi, pierce, and wadler, and its recent extension feathertrait java (ftj) by the authors, we investigate classes that can be extended with trait composition. a trait is a collection of methods, i.e., behaviors without state; it can be viewed as an ''incomplete stateless class'' i.e., an interface with some already written behavior. traits can be composed in any order, but only make sense when ''imported'' by a class that provides state variables and additional methods to disambiguate conflicting names arising between the imported traits. we introduce feathertrait java with interfaces (iftj), where traits need to be typechecked only once, which is necessary for compiling them in isolation, and considering them as regular types, like java-interfaces with a behavioral content.