waashk/dblp huggingface dataset:
the black-box complexity of nearest-neighbor search. we define a natural notion of efficiency for approximate nearest-neighbor (ann) search in general n-point metric spaces, namely the existence of a randomized algorithm which answers (1 + ε)-ann queries in polylog(n) time using only polynomial space. we then study which families of metric spaces admit efficient ann schemes in the black-box model, where only oracle access to the distance function is given, and any query consistent with the triangle inequality may be asked.for ε < 2/5, we offer a complete answer to this problem. using the notion of metric dimension defined in [a. gupta, et al., bounded geometries, fractals, and low-distortion embeddings, in: 44th annu. ieee symp. on foundations of computer science, 2003, pp. 534-543] (à la [p. assouad, plongements lipschitziens dans rn, bull. soc. math. france 111 (4) (1983) 429-448]), we show that a metric space x admits an efficient (1+ε)-ann scheme for any ε < 2/5 if and only if dim(x) = o(log log n). for coarser approximations, clearly the upper bound continues to hold, but there is a threshold at which our lower bound breaks down--this is precisely when points in the "ambient space" may begin to affect the complexity of "hard" subspaces s ⊆ x. indeed, we give examples which show that dim(x) does not characterize the black-box complexity of ann above the threshold.our scheme for ann in low-dimensional metric spaces is the first to yield efficient algorithms without relying on any additional assumptions on the input. in previous approaches (e.g., [k.l. clarkson, nearest neighbor queries in metric spaces, discrete comput. geom. 22(1) (1999) 63-93; d. karger, m. ruhl, finding nearest neighbors in growth-restricted metrics, in: 34th annu. acm symp. on the theory of computing, 2002, pp. 63-66; r. krauthgamer, j.r. lee, navigating nets: simple algorithms for proximity search, in: 15th annu. acm-siam symp. on discrete algorithms, 2004, pp. 791-801; k. hildrum, et al., a note on finding nearest neighbors in growth-restricted metrics, in: proc. of the 15th annu. acm-siam symp. on discrete algorithms, 2004, pp. 560-561]), even spaces with dim(x) = o(1) sometimes required ω(n) query times.
breaking des using p systems. membrane systems, also called p systems, were introduced by gh. paun, as a new class of biologically inspired distributed computing models. several variants of p systems were already shown to be computationally universal. one of these variants, introduced in gh. paun (j. automata languages combin. 6 (1) (2001) 75), is able to solve sat in linear time. in this paper, we show how this class of p systems (with membrane division) can theoretically break the most widely used cryptosystem, des. we prove that given an arbitrary (plain-text, cipher-text) pair, one can recover the des key in linear time with respect to the length of the key.
automatic synthesis of a subclass of schedulers in timed systems. in this article we present a synthesis technique for generating schedulers for real-time systems. the aim of the scheduler is to ensure (via restricting the general behaviour) that the real-time system satisfies the specification. the real-time system and the specification are described as alur-dill timed automata while the synthesised scheduler is a type of timed trajectory automaton. this allows us to perform the synthesis without incurring the cost of constructing timed regions. we also note a simple constraint that the specification has to satisfy for this technique to be useful.
on the computational complexity of imperative programming languages. two restricted imperative programming languages are considered: one is a slight modification of a loop language studied intensively in the literature, the other is a stack programming language over an arbitrary but fixed alphabet, supporting a suitable loop concept over stacks. the paper presents a purely syntactical method for analysing the impact of nesting loops on the running time. this gives rise to a uniform measure µ on both loop and stack programs, that is, a function that assigns to each such program p a natural number µ(p) computable from the syntax of p.it is shown that stack programs of µ-measure n compute exactly those functions computed by a turing machine whose running time lies in grzegorczyk class εn-2. in particular, stack programs of µ-measure 0 compute precisely the polynomial-time computable functions.furthermore, it is shown that loop programs of µ-measure n compute exactly the functions in εn-2. in particular, loop programs of µ-measure 0 compute precisely the linear-space computable functions.
effective simultaneous approximability of reals. the effective simultaneous approximability of real vectors and sets of reals is studied. a hierarchy of real vectors based on the kolmogorov complexity of computable approximations is constructed. we prove that the hierarchy is nontrivial at the bottom levels but collapses on the top levels. a hierarchy theorem which gives a simple test for proper inclusion between two classes is established. we also show that an effective approximation problem for a finite set may be hard (have no computable solutions) when the corresponding problems for all its proper subsets are simple (have computable solutions).
on the complexity of the reflected logic of proofs. artemov's propositional logic of proofs lp captures all invariant properties of proof predicates "t is a proof of f" which are represented in lp as formulas t: f. kuznets in [on the complexity of explicit modal logics, in: computer science logic 2000, lecture notes in computer science, vol. 1862, springer, berlin, 2000, pp. 371-383] showed that the satisfiability problem for lp belongs to the class π2p of the polynomial hierarchy. in this paper we consider the reflected logic of proofs, rlp, consisting of formulas t: f derivable in lp. the system rlp is as expressible as lp itself, since every f derivable in lp is represented in rlp by t: f for an appropriate proof term t. we prove a better upper bound (np) for the decision procedure in rlp. in addition we prove the disjunctive property for the original logic of proofs lp, thus answering a well-known question in this area.
referential logic of proofs. we introduce an extension of the propositional logic of single-conclusion proofs by the second-order variables denoting the reference constructors of the type "the formula which is proved by x." the resulting logic of proofs with references, flpref, is shown to be decidable, and to enjoy soundness and completeness with respect to the intended provability semantics. we show that flpref provides a complete test of admissibility of inference rules in a sound extension of arithmetic. this paper may be regarded as a contribution to the theory of automated reasoning systems.
efficient approximation algorithms for the achromatic number. the achromatic number problem is, given a graph g = (v, e), to find the greatest number of colors, ψ(g), in a coloring of the vertices of g such that adjacent vertices get distinct colors and for every pair of colors some vertex of the first color and some vertex of the second color are adjacent. this problem is np-complete even for trees. we obtain the following new results using combinatorial approaches to the problem. (1) a polynomial time o(|v|3/8)-approximation algorithm for the problem on graphs with girth at least six. (2) a polynomial time 2-approximation algorithm for the problem on trees. this is an improvement over the best previous 7-approximation algorithm. (3) a linear time asymptotic 1.414-approximation algorithm for the problem when graph g is a tree with maximum degree d(|v|), where d : n → n, such that d(|v|) = o(ψ(g)). for example, d(|v|) = θ(1) or d(|v|) = θ(log |v|). (4) a linear time asymptotic 1.118-approximation algorithm for binary trees. we also improve the lower bound on the achromatic number of binary trees.
reconstruction of convex 2d discrete sets in polynomial time. the reconstruction problem is considered in those classes of discrete sets where the reconstruction can be performed from two projections in polynomial time. the reconstruction algorithms and complexity results are summarized in the case of hv-convex sets, hv-convex 8-connected sets, hv-convex polyominoes, and directed h-convex sets. as new results some properties of the feet and spines of the hv-convex 8-connected sets are proven and it is shown that the spine of such a set can be determined from the projections in linear time. two algorithms are given to reconstruct hv-convex 8-connected sets. finally, it is shown that the directed h-convex sets are uniquely reconstructible with respect to their row and column sum vectors.
a sufficient condition for non-uniqueness in binary tomography with absorption. a new kind of discrete tomography problem is introduced: the reconstruction of discrete sets from their absorbed projections. a special case of this problem is discussed, namely, the uniqueness of the binary matrices with respect to their absorbed row and column sums when the absorption coefficient is µ = log((1 + √5)/2). it is proved that if a binary matrix contains a special structure of 0s and 1s, called alternatively corner-connected component, then this binary matrix is non-unique with respect to its absorbed row and column sums. since it has been proved in another paper [a. kuba, m. nivat, reconstruction of discrete sets with absorption, linear algebra appl. 339 (2001) 171-194] that this condition is also necessary, the existence of alternatively corner-connected component in a binary matrix gives a characterization of the non-uniqueness in this case of absorbed projections.
the complexity of bisimilarity-checking for one-counter processes. we study the problem of bisimilarity-checking between processes of one-counter automata and finite-state processes. we show that deciding weak bisimilarity between processes of one-counter nets (which are 'restricted' one-counter automata where the counter cannot be tested for zero) and finite-state processes is dp-hard. in particular, this means that the problem is both np and co-np hard. the same technique is used to demonstrate co-np-hardness of strong bisimilarity between processes of one-counter nets. then we design an algorithm which decides weak bisimilarity between processes of one-counter automata and finite-state processes in time which is polynomial for a large subclass of instances, giving a kind of characterization of all hard instances as a byproduct. moreover, we show how to efficiently estimate the time which is needed to solve a given instance. finally, we prove that the problem of strong bisimilarity between processes of one-counter automata and finite-state processes is in p.
weak bisimilarity between finite-state systems and bpa or normed bpp is decidable in polynomial time. we prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes and normed basic parallel processes (normed bpp). to the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.
data abstractions for decision tree induction. when descriptions of data values in a database are too concrete or too detailed, the computational complexity needed to discover useful knowledge from the database will be generally increased. furthermore, discovered knowledge tends to become complicated. a notion of data abstraction seems useful to resolve this kind of problems, as we obtain a smaller and more general database after the abstraction, from which we can quickly extract more abstract knowledge that is expected to be easier to understand. in general, however, since there exist several possible abstractions, we have to carefully select one according to which the original database is generalized. an inadequate selection would make the accuracy of extracted knowledge worse.from this point of view, we propose in this paper a method of selecting an appropriate abstraction from possible ones, assuming that our task is to construct a decision tree from a relational database. suppose that, for each attribute in a relational database, we have a class of possible abstractions for the attribute values. as an appropriate abstraction for each attribute, we prefer an abstraction such that, even after the abstraction, the distribution of target classes necessary to perform our classification task can be preserved within an acceptable error range given by user.by the selected abstractions, the original database can be transformed into a small generalized database written in abstract values. therefore, it would be expected that, from the generalized database, we can construct a decision tree whose size is much smaller than one constructed from the original database. furthermore, such a size reduction can be justified under some theoretical assumptions. the appropriateness of abstraction is precisely defined in terms of the standard information theory. therefore, we call our abstraction framework information theoretical abstraction.we show some experimental results obtained by a system ita that is an implementation of our abstraction method. from those results, it is verified that our method is very effective in reducing the size of detected decision tree without making classification errors so worse.
toward a theory of intelligence. in 1950, turing suggested that intelligent behavior might require "a departure from the completely disciplined behavior involved in computation", but nothing that a digital computer could not do. in this paper, i want to explore turing's suggestion by asking what it is, beyond computation, that intelligence might require, why it might require it and what knowing the answers to the first two questions might do to help us understand artificial and natural intelligence.
analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem. multiobjective evolutionary algorithms (moeas) are increasingly being used for effectively solving many real-world problems, and many empirical results are available. however, theoretical analysis is limited to a few simple toy functions. in this work, we select the well-known knapsack problem for the analysis. the multiobjective knapsack problem in its general form is np-complete. moreover, the size of the set of pareto-optimal solutions can grow exponentially with the number of items in the knapsack. thus, we formalize a (1 + ε)-approximate set of the knapsack problem and attempt to present a rigorous running time analysis of a moea to obtain the formalized set. the algorithm used in the paper is based on a restricted mating pool with a separate archive to store the remaining population; we call the algorithm a restricted evolutionary multiobjective optimizer (remo). we also analyze the running time of remo on a special bi-objective linear function, known as lotz (leading ones : trailing zeros), whose pareto set is shown to be a subset of the knapsack. an extension of the analysis to the simple evolutionary multiobjective optimizer (semo) is also presented. a strategy based on partitioning of the decision space into fitness layers is used for the analysis.
the topology of mazurkiewicz traces. the present paper characterizes the topological structure of real traces. this is done in terms of graph-theoretic properties of the underlying (possibly infinite) dependence alphabet. the topological space of real traces is shown to be homeomorphic to the direct product of (at most) the full binary tree and the full countably branching tree and one higher-dimensional grid. the occurrence of each of these factors depends on the existence of finite non-trivial and of infinite connected components and on the number of isolated letters of the dependence alphabet.
undecidability of the trace coding problem and some decidable cases. we introduce and investigate the notion of weak morphisms of trace monoids with the aim of dealing with the problem of deciding the existence of codings between trace monoids. we prove that this problem is not recursively enumerable, which answers the question raised by ochmanski in 1988. on the other hand, we show its decidability when restricted to instances with domain monoids defined by acyclic dependence graphs. we also partially answer the question of diekert from 1990 about the number of free monoids needed for encoding a given trace monoid into their direct product.
regular solutions of language inequalities and well quasi-orders. by means of constructing suitable well quasi-orders of free monoids we prove that all maximal solutions of certain systems of language inequalities are regular. this way we deal with a wide class of systems of inequalities where all constants are languages recognized by finite simple semigroups. in a similar manner we also demonstrate that the largest solution of the inequality xk ⊆ lx is regular provided the language l is regular.
refinement calculus: a basis for translation validation, debugging and certification. in this paper, we show how refinement calculus provides a basis for translation validation of optimized programs written in high level languages. towards such a direction, we shall provide a generalized proof rule for establishing refinement of source and target programs for which one need not have to know the underlying program transformations. our method is supported by a semi-automatic tool that uses a theorem prover for validating the verification conditions. we further show that the translation validation infrastructure provides an effective basis for deriving semantic debuggers and illustrate the development of a simple debugger for optimized programs using this approach using prolog. a distinct advantage of semantic debugging is that it permits the user to change values at run-time only when the values are consistent with the underlying semantics.
partial quasi-metrics. in this article we introduce and investigate the concept of a partial quasi-metric and some of its applications. we show that many important constructions studied in matthews's theory of partial metrics can still be used successfully in this more general setting. in particular, we consider the bicompletion of the quasi-metric space that is associated with a partial quasi-metric space and study its applications in groups and bck-algebras.
on the complexity of queries in the logical data model. we investigate the complexity of query processing in the logical data model (ldm). we use two measures: data complexity, which is complexity with respect to the size of the data, and expression complexity, which is complexity with respect to the size of the expressions denoting the queries. our investigation shows that while the operations of product and union are essentially first-order operations, the power set operation is inherently a higher-order operation and is exponentially expensive. we define a hierarchy of queries based on the depth of nesting of power set operations and show that this hierarchy corresponds to a natural hierarchy of turing machines that run in multiply exponential time.
from complementation to certification. in the automata-theoretic approach to model checking we check the emptiness of the product of a system s with an automaton a-ψ for the complemented specification. this gives rise to two automata-theoretic problems: complementation of word automata, which is used in order to generate a-ψ, and the emptiness problem, to which model checking is reduced. both problems have numerous other applications, and have been extensively studied for nondeterministic büchi word automata (nbw). nondeterministic generalized büchi word automata (ngbw) have become popular in specification and verification and are now used in applications traditionally assigned to nbw. this is due to their richer acceptance condition, which leads to automata with fewer states and a simpler underlying structure.in this paper we analyze runs of ngbw and use the analysis in order to describe a new complementation construction and a symbolic emptiness algorithm for ngbw. the complementation construction exponentially improves the best known construction for ngbw and is easy to implement. the emptiness algorithm is almost identical to a known variant of the emerson-lei algorithm, and our contribution is the strong relation we draw between the complementation construction and the emptiness algorithm--both naturally follow from the analysis of the runs, which easily implies their correctness. this relation leads to a new certified model-checking procedure, where a positive answer to the model-checking query is accompanied by a certificate whose correctness can be checked by methods independent of the model checker. unlike certificates generated in previous works on certified model checking, our analysis enables us to generate a certificate that can be checked automatically and symbolically.
stone coalgebras. we argue that the category of stone spaces forms an interesting base category for coalgebras, in particular, if one considers the vietoris functor as an analogue to the power set functor on the category of sets.we prove that the so-called descriptive general frames, which play a fundamental role in the semantics of modal logics, can be seen as stone coalgebras in a natural way. this yields a duality between modal algebras and coalgebras for the vietoris functor.building on this idea, we introduce the notion of a vietoris polynomial functor over the category of stone spaces. for each such functor t we provide an adjunction between t-sorted boolean algebras with operators and the stone coalgebras for t. we also identify the subcategory of algebras on which the adjunction restricts to an equivalence and show that the final t-coalgebra is the dual of the initial t-bao.
towards a language theory for infinite n-free pomsets. n-free or series-parallel pomsets are a model for the behavior of modularly constructed concurrent systems. the investigation of recognizable languages of finite n-free pomsets was initiated by lodaya and weil who extended the theorems by kleene and by myhill and nerode on recognizable word languages to this setting. in this paper, we extend lodaya and weil's results in several aspects: (a) we consider the relation of recognizable sets to monadic second order logic in order to generalize büchi's theorem. (b) we prove our results (and extensions of results by lodaya and weil) for sets of infinite n-free pomsets. and (c), we investigate first-order axiomatizable, starfree, and aperiodic sets of infinite n-free pomsets and prove results in the spirit of mcnaughton and papert's and schützenberger's theorems for finite words.
on the descriptional power of heads, counters, and pebbles. we investigate the descriptional complexity of deterministic two-way k-head finite automata (k- dha). it is shown that between non-deterministic pushdown automata and any k-dha, k ≥ 2, there are savings in the size of description which cannot be bounded by any recursive function. the same is true for the other end of the hierarchy. such non-recursive trade-offs are also shown between any k-dha, k ≥ 1, and dspace(log) = multi-dha. we also address the particular case of unary languages. in general, it is possible that non-recursive trade-offs for arbitrary languages reduce to recursive trade-offs for unary languages. here we present huge lower bounds for the unary trade-offs between non-deterministic finite automata and any k-dha, k ≥ 2. furthermore, several known simulation results imply the presented trade-offs for other descriptional systems, e.g., deterministic two-way finite automata with k pebbles or with k linearly bounded counters.
the complexity of boolean matrix root computation. we show that finding roots of boolean matrices is an np-hard problem. this answers a 20 year old question from semigroup theory. interpreting boolean matrices as directed graphs, we further reveal a connection between boolean matrix roots and graph isomorphism, which leads to a proof that for a certain subclass of boolean matrices related to subdivision digraphs, root finding is of the same complexity as the graph-isomorphism problem.