waashk/dblp huggingface dataset:
polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. a formula (in conjunctive normal form) is said to be minimal unsatisfiable if it is unsatisfiable and deleting any clause makes it satisfiable. the deficiency of a formula is the difference of the number of clauses and the number of variables. it is known that every minimal unsatisfiable formula has positive deficiency. until recently, polynomial-time algorithms were known to recognize minimal unsatisfiable formulas with deficiency 1 and 2. we state an algorithm which recognizes minimal unsatisfiable formulas with any fixed deficiency in polynomial time.
sense of direction in distributed computing. sense of direction is a property of labeled graphs which has been shown to have a definite impact on computability and complexity in systems of communicating entities, and whose applicability ranges from the analysis of graph classes to distributed object systems. the full consequences of this property are still not known; in fact, the ongoing investigations continue to bring new (often surprising) results, to establish unsuspected links with other research and/or application areas, and to pose more questions than they answer. the aim of this paper is to provide a view of the current status of research, describing some of the relevant results, and providing pointers to future research directions.
gathering of asynchronous robots with limited visibility. in this paper we study the problem of gathering a collection of identical oblivious mobile robots in the same location of the plane. previous investigations have focused mostly on the unlimited visibility setting, where each robot can always see all the others regardless of their distance.in the more difficult and realistic setting where the robots have limited visibility, the existing algorithmic results are only for convergence (towards a common point, without ever reaching it) and only for semi-synchronous environments, where robots' movements are assumed to be performed instantaneously.in contrast, we study this problem in a totally asynchronous setting, where robots' actions, computations, and movements require a finite but otherwise unpredictable amount of time. we present a protocol that allows anonymous oblivious robots with limited visibility to gather in the same location in finite time, provided they have orientation (i.e., agreement on a coordinate system).our result indicates that, with respect to gathering, orientation is at least as powerful as instantaneous movements.
computing on anonymous networks with sense of direction. sense of direction refers to a set of global consistency constraints of the local labeling of the edges of a network. sense of direction has a large impact on the communication complexity of many distributed problems. in this paper, we study the impact that sense of direction has on computability and we focus on anonymous networks. we establish several results. in particular, we prove that with weak sense of direction, the intuitive knowledge-computability hierarchy between levels of a priori structural knowledge collapses. a powerful implication is the formal proof that shortest path routing is possible in anonymous networks with sense of direction. we prove that weak sense of direction is computationally stronger than topological awareness. we also consider several fundamental problems; for each, we provide a complete characterization of the anonymous networks on which it is computable with sense of direction.
limiting distributions for additive functionals on catalan trees. additive tree functionals represent the cost of many divide-and-conquer algorithms. we derive the limiting distribution of the additive functionals induced by toll functions of the form (a) nα when α > 0 and (b) log n (the so-called shape functional) on uniformly distributed binary trees, sometimes called catalan trees. the gaussian law obtained in the latter case complements the central limit theorem for the shape functional under the random permutation model. our results give rise to an apparently new family of distributions containing the airy distribution (α = 1) and the normal distribution [case (b), and case (a) as α ↓ 0]. the main theoretical tools employed are recent results relating asymptotics of the generating functions of sequences to those of their hadamard product, and the method of moments.
exact and approximate balanced data gathering in energy-constrained sensor networks. we consider the problem of gathering data from a wireless multi-hop network of energy-constrained sensor nodes to a common base station. specifically, we aim to balance the total amount of data received from the sensor network during its lifetime against a requirement of sufficient coverage for all the sensor locations surveyed. our main contribution lies in formulating this balanced data gathering task, studying the effects of balancing, and proposing an approximation algorithm for the problem. based on an lp network flow formulation, we present experimental results on both optimal and approximate data routing designs, in open transmission ranges and with impenetrable obstacles between the nodes.
query by committee, linear separation and random walks. a long-standing goal in the realm of machine learning is to minimize sample-complexity, i.e. to reduce as much as possible the number of examples used in the course of learning. the active learning paradigm is one such method aimed at achieving this goal by transforming the learner from a passive participant in the information gathering process to an active one. vaguely speaking, the learner tries to minimize the number of labeled instances used in the course of learning, relaying also on unlabelled instances in order to acquire the needed information whenever possible. the reasoning comes from many real-life problems where the teacher's activity is an expensive resource (e.g. text categorization, part of speech tagging). the query by committee (qbc) (seung et al., query by committee, proceedings of the fifth workshop on computational learning theory, morgan kaufman, san mateo, ca, 1992, pp. 287-294) is an active learning algorithm acting in the bayesian model of concept learning (haussler et al., mach. learning 14 (1994) 83), i.e. it assumes that the concept to be learned is chosen according to some fixed and known distribution. trying to apply the qbc algorithm for learning the class of linear separators, one faces the problem of implementing the mechanism of sampling hypotheses (the gibbs oracle). the major problem is computational-complexity, since the straightforward monte carlo method takes exponential time. in this paper we address the problems involved in the implementation of such a mechanism. we show how to convert them to questions about sampling from convex bodies or approximating the volume of such bodies. similar problems have recently been solved in the field of computational geometry based on random walks. these techniques enable us to device efficient implementations of the qbc algorithm. we also give few improvements and corrections to the qbc algorithm, the most important one is dropping the bayes assumption when the concept classes possess a sort of symmetry property (which holds for linear separators). we draw attention to a useful geometric lemma which bounds the maximal radius of a ball contained in a convex body. finally, this paper exhibits a connection between random walks and certain machine learning notions such as ε-net and support vector machines.
the universe of propositional approximations. the idea of approximate entailment has been proposed by schaerf and cadoli [tractable reasoning via approximation, artif. intell. 74(2) (1995) 249-310] as a way of modelling the reasoning of an agent with limited resources. in that framework, a family of logics, parameterised by a set of propositional letters, approximates classical logic as the size of the set increases.the original proposal dealt only with formulas in clausal form, but in finger and wassermann [approximate and limited reasoning: semantics, proof theory, expressivity and control, j. logic comput. 14(2) (2004) 179-204], one of the approximate systems was extended to deal with full propositional logic, giving the new system semantics, an axiomatisation, and a sound and complete proof method based on tableaux. in this paper, we extend another approximate system by schaerf and cadoli, presented in a subsequent work [m. cadoli, m. schaerf, the complexity of entailment in propositional multivalued logics, ann. math. artif. intell. 18(1) (1996) 29-50] and then take the idea further, presenting a more general approximation framework of which the previous ones are particular cases, and show how it can be used to formalise heuristics used in theorem proving.
a comparison of three authentication properties. authentication is a slippery security property that has been formally defined only recently; among the recent definitions, two rather interesting ones have been proposed for the spi-calculus by (abadi and gordon (in: proc. concur'97, lecture notes in computer science, vol. 1243, springer, berlin, 1997, pp. 59-73; inform. and comput. 148(1) (1999) 1-70) and for csp by lowe (in: proc. 10th computer security foundation workshop, ieee press, 1997, pp. 31-43). on the other hand, in a recent paper (in: proc. world congr. on formal methods (fm'99), lecture notes in computer science, vol. 1708, springer, berlin, 1999, pp. 794-813), we have proved that many existing security properties can be seen uniformly as specific instances of a general scheme based on the idea of non-interference. the purpose of this paper is to show that, under reasonable assumptions, spi-authentication can be recast in this general framework as well, by showing that it is equivalent to the non-interference property called ndc of focardi and gorrieri (j. comput. security 3(1) (1994/1995) 5-33; ieee trans. software eng. 23(9) (199) 550-571). this allows for the comparison between such a property and the one based on csp, which was already recast under the general scheme of focardi and martinelli (1999).
compositionality of hennessy-milner logic by structural operational semantics. this paper presents a method for the decomposition of hml formulas. it can be used to decide whether a process algebra term satisfies a hml formula, by checking whether subterms satisfy certain formulas, obtained by decomposing the original formula. the method uses the structural operational semantics of the process algebra. the main contribution of this paper is the extension of an earlier decomposition method for the de simone format from the ph.d. thesis of larsen in 1986, to more general formats.
borel hierarchy and omega context free languages. we give in this paper additional answers to questions of lescow and thomas (a decade of concurrency, lecture notes in computer science, vol. 803, springer, berlin, 1994, pp. 583-621), proving topological properties of omega context free languages (ω-cfl) which extend those of o. finkel (theoret. comput. sci. 262 (1-2) (2001) 669-697): there exist some ω-cfl which are non borel sets and one cannot decide whether an ω-cfl is a borel set. we give also an answer to a question of niwinski (problem on ω-powers posed in the proceedings of the workshop "logics and recognizable sets, 1990") and of simonnet (automates et thérie descriptive, ph.d. thesis, université paris 7, 1992) about ω-powers of finitary languages, giving an example of a finitary context free language l such that lω is not a borel set. then we prove some recursive analogues to preceding properties: in particular one cannot decide whether an ω-cfl is an arithmetical set. finally we extend some results to context free sets of infinite trees.
ambiguity in omega context free languages. we extend the well-known notions of ambiguity and of degrees of ambiguity of finitary context free languages to the case of omega context free languages (ω-cfl) accepted by büchi or muller pushdown automata. we show that these notions may be defined independently of the büchi or muller acceptance condition which is considered. we investigate first properties of the subclasses of omega context free languages we get in that way, giving many examples and studying topological properties of ω-cfl of a given degree of ambiguity.
on omega context free languages which are borel sets of infinite rank. this paper is a continuation of the study of topological properties of omega context free languages (ω-cfl). we proved in (topological properties of omega context free languages, theoretical computer science, 262 (1-2) (2001) 669-697) that the class of ω-cfl exhausts the finite ranks of the borel hierarchy, and in (borel hierarchy and omega context free languages, theoretical computer science, to appear) that there exist some ω-cfl which are analytic but non borel sets. we prove here that there exist some omega context free languages which are borel sets of infinite (but not finite) rank, giving additional answer to questions of lescow and thomas [logical specifications of infinite computations in: "a decade of concurrency" (j.w. de bakker et al. (eds.), springer lncs 803 (1994) 583-621).
on the sensitivity of additive cellular automata in besicovitch topologies. we prove that additive cellular automata in the besicovitch topology that have a willson limit set of hausdorff dimension strictly bigger than 1 are sensitive to initial conditions.
number conserving cellular automata ii: dynamics. in this second part, we study the dynamics of the number conserving cellular automata. we give a classification which focuses on pattern divergence and chaoticity. moreover we prove that in the case of number-conserving cellular automata, surjectivity is equivalent to regularity. as a byproduct we obtain a strong characterization of the class of cellular automata with bounded evolutions on finite configurations.
on decidability properties of local sentences. local (first order) sentences, introduced by ressayre, enjoy very nice decidability properties, following from some stretching theorems stating some remarkable links between the finite and the infinite model theory of these sentences [j.-p. ressayre, formal languages defined by the underlying structure of their words, j. symbolic logic 53 (4) (1988) 1009-1026]. another stretching theorem of finkel and ressayre implies that one can decide, for a given local sentence ϕ and an ordinal α < ωω, whether ϕ has a model of order type α. this result is very similar to büchi's one who proved that the monadic second order theory of the structure (α, <), for a countable ordinal α, is decidable. it is in fact an extension of that result, as shown in [o. finkel, finite languages, theoret. comput. sci. 255 (1-2) (2001) 223-261] by considering the expressive power of monadic sentences and of local sentences over languages of words of length α. the aim of this paper is twofold. we wish first to attract the reader's attention on these powerful decidability results proved using methods of model theory and which should find some applications in computer science and we prove also here several additional results on local sentences.the first one is a new decidability result in the case of local sentences whose function symbols are at most unary: one can decide, for every regular cardinal ωα (the αth infinite cardinal), whether a local sentence ϕ has a model of order type ωα.secondly we show that this result cannot be extended to the general case. assuming the consistency of an inaccessible cardinal we prove that the set of local sentences having a model of order type ω2 is not determined by the axiomatic system zfc + gch, where gch is the generalized continuum hypothesis.next we prove that for all integers n, p ≥ 1, if n < p then the local theory of ωn, i.e. the set of local sentences having a model of order type ωn, is recursive in the local theory of ωp and also in the local theory of α where α is any ordinal of cofinality ωn.
better-quasi-orderings and coinduction. we can characterise the class of bqos as the largest class of well-founded quasiorders closed under the hoare powerdomain construction and colimits.
on the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. this paper discusses theoretical limitations of classification systems that are based on feature maps and use a separating hyperplane in the feature space. in particular, we study the embeddability of a given concept class into a class of euclidean half spaces of low dimension, or of arbitrarily large dimension but realizing a large margin. new bounds on the smallest possible dimension or on the largest possible margin are presented. in addition, we present new results on the rigidity of matrices and briefly mention applications in complexity and learning theory.
independent triangles covering given vertices of a graph. let g be a simple graph of order n, k a positive integer with n&ge;3k and x a set of any k vertices of g. we show that if the minimum degree g)&ge;(n + k)=2, then g contains k independent triangles covering all vertices of x ; and if the minimum degree (g)&ge;(n+2k)=2, then g contains k independent triangles such that each triangle contains exactly one vertex of x . the bounds on the minimum degree of g in above results are sharp. some conjectures about independent triangles covering some given vertices are proposed.
a new framework for declarative programming. we propose a new framework for the syntax and semantics of weak hereditarily harrop logic programming with constraints, based on resolution over τ-categories: finite product categories with canonical structure.constraint information is directly built-in to the notion of signature via categorical syntax. many-sorted equational are a special case of the formalism which combines features of uniform logic programming languages (moduels and hypothetical implication) with those of constraint logic programming. using the cannoical structure supplied by τ-categories, we define a diagrammatic generalization of formulas, goals, programs and resolution proofs up to equality (rather than just up to isomorphism).we extend the kowalski-van emden fixed point interpretation, a cornerstone of declarative semantics, to an operational, non-ground, categorical semantics based on indexing over sorts and programs.we also introduce a topos-theoretic declarative semantics and show soundness and completeness of resolution proofs and of a sequent calculus over the categorical signature. we conclude with a discussion of semantic perspectives on uniform logic programming.
on the bahncard problem. in this paper, we generalize the ski-rental problem to the bahncard problem which is an online problem of practical relevance for all travelers. the bahncard is a railway pass of the deutsche bundesbahn (the german railway company) which entitles its holder to a 50% price reduction on nearly all train tickets. it costs 240dm, and it is valid for 12 months. similar bus or railway passes can be found in many other countries. for the common traveler, the decision at which time to buy a bahncard is a typical online problem, because she usually does not know when and where she will travel next. we show that the greedy algorithm applied by most travelers and clerks at ticket offices is not better in the worst case than the trivial algorithm which never buys a bahncard. we present two optimal deterministic online algorithms, an optimistic one and a pessimistic one. we further give a lower bound for randomized online algorithms and present an algorithm which we conjecture to be optimal; a proof of the conjecture is given for a special case of the problem. it turns out that the optimal competitive ratio only depends on the price reduction factor (50% for the german bahncard problem), but does not depend on the price or validity period of a bahncard. copyright 2001 elsevier science b.v.
determination of equivalence between quantum sequential machines. quantum sequential machines (qsms) that may be viewed as a quantum variant of stochastic sequential machines (ssms) are one of the important quantum computing models. a very crucial result on ssms is that two ssms with n and n' states, respectively, and the same input and output alphabets are equivalent if and only if they are (n + n' - 1)-equivalent. therefore, gudder asked whether or not it holds for qsms, as an open problem in this direction, since the further study is closely related to this result. qiu demonstrated that in qsms this result does not hold, and therefore answered in part the problem. however, as qiu indicated, the sufficient and necessary conditions for the equivalence between two qsms are still not discovered. in this paper, we show that if the condition of (n + n' -1)-equivalence is appropriately relaxed, then we can give a sufficient and necessary condition for justifying the equivalence between two qsms. more precisely, we show that any two qsms m and m' are equivalent if and only if they are (n + n')2-equivalent, where n and n' are, respectively, the numbers of states in m and m'. we therefore solve the open problem suggested by gudder, and provide a basic result for further developing qsms. as well, we discuss strongly factorizable qsms and present the conditions for the equivalence between two strongly factorizable qsms.
from hopfield nets to recursive networks to graph machines: numerical machine learning for structured data. the present paper is a short survey of the development of numerical learning from structured data, an old problem that was first addressed by the end of the years 1980, and has recently undergone exciting developments, both from a theoretical point of view and for applications. traditionally, numerical machine learning deals with unstructured data, in the form of vectors: neural networks, graphical models, support vector machines, handle vectors of features that are assumed to be relevant for solving the problem at hand (classification or regression). it is often the case, however, that data is structured, i.e. is in the form of graphs; three examples will be described here: prediction of the properties of molecules, image analysis, and natural language processing. the traditional approach consists in handcrafting a vector representation of the structured data (features describing the molecules, "bag of words" for language processing), and subsequently training a machine to perform the task from that representation. by contrast, we describe here a family of approaches (raams, lraams, recursive or folding networks, graph machines) that are specifically designed to learn from structured data. we show that, despite the apparent diversity, two basic principles underlie the recent approaches: first, use structured machines to learn structured data; second, learn representations instead of handcrafting them; although neither principle is really new, they proved very successful for handling structured data, to the point of generating a novel branch of numerical machine learning.
one complexity theorist's view of quantum computing. the complexity of quantum computation remains poorly understood. while physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. the tools of computational complexity theory should come to bear on these important questions.quantum computing often scares away many potential researchers in computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic.this paper will give an overview of quantum computation from the point of view of a complexity theorist. we will see that one can think of bqp as yet another complexity class and study its power without focusing on the physical aspects behind it.