waashk/dblp huggingface dataset:
a note on natural complete sets and gödel numberings. creative sets (or the complete recursively enumerable sets) play an important role in logic and mathematics and they are known to be recursively isomorphic. therefore, on the one hand, all the creative sets can be viewed as equivalent, on the other hand, we intuitively perceive some creative sets as more ``natural and simpler'''' than others. in this note, we try to capture this intuitive concept precisely by defining a creative set to be natural if all other recursively enumerable sets can be reduced to it by computationally simple reductions and show that these natural creative sets are all isomorphic under the same type of computationally simple mappings. the same ideas are also applied to define natural goedel numberings.
on gödel speed-up and succinctness of language representations. in this note we discuss the similarities and differences between goedel''s result about non-recursive shortening of proofs of formal systems by additional axioms and the corresponding results about the succinctness of different representations of languages.
computation times of np sets of different densities. in this paper, we study the computational complexity of sets of different densities in np. we show that the deterministic computation time for sets in np can depend on their density if and only if there is a collapse or partial collapse of the corresponding higher nondeterministic and deterministic time bonded complexity classes. we show also that for np sets of different densities there exist complete sets of the corresponding density under polynomial time turing reductions. finally, we show that these results can be interpreted as results about the complexity of theorem proving and proof presentation in axiomatized mathematical systems. this interpretation relates fundamental questions about the complexity of our intellectual tools to basic structural problems about p, np, conp, and pspace, discussed in this paper.
erratum to "axiomatisations of functional dependencies in the presence of records, lists, sets and multisets". this note corrects two errors that occurred during the typesetting of our paper "axiomatisations of functional dependencies in the presence of records, lists, sets and multisets", which appeared in hartmann et al. [axiomatisations of functional dependencies in the presence of records, lists, sets and multisets, theoret. comput. sci. 353(2) (2006) 167-196].
towards categorical models for fairness: fully abstract presheaf semantics of sccs with finite delay. we present a presheaf model for the observation of infinite as well as finite computations. we give a concrete representation of the presheaf model as a category of generalised synchronisation trees and show that it is coreflective in a category of generalised transition systems, which are a special case of the general transition systems of hennessy and stirling. this can be viewed as a first step towards representing fairness in categorical models for concurrency. the open map bisimulation is shown to coincide with extended bisimulation of hennessy and stirling, which is essentially fair ctl*-bisimulation. we give a denotational semantics of milner's sccs with finite delay in the presheaf model, which differs from previous semantics by giving the meanings of recursion by final coalgebras and meanings of finite delay by initial algebras of the process equations for delay. finally, we formulate milner's operational semantics of sccs with finite delay in terms of generalised transition systems and prove that the presheaf semantics is fully abstract with respect to extended bisimulation.
split algorithms for skewsymmetric toeplitz matrices with arbitrary rank profile. split levinson-type and schur-type algorithms for the solutions of linear systems with a nonsingular skewsymmetric toeplitz matrix are designed. in contrast to previous ones, the algorithms work for any nonsingular skewsymmetric toeplitz matrix. moreover, generalizations of zw- and wz-factorizations of skewsymmetric toeplitz matrices related to the new split algorithms are presented.
quadrature using 64-bit ieee arithmetic for integrands over [0, 1] with a singularity at 1. we present a detailed study of some problems encountered when quadrature over [0, 1] is attempted with integrands that have a singularity at 1. methods designed to increase the accuracy of such quadratures, for example, the application of periodising transformations, are examined in the context of the representational limitations of 64-bit ieee arithmetic near 1 in [0, 1 ]. a heuristic is proposed for the forecasting of a lower bound on the irremovable error due to these limitations. we conclude by affirming the commonly accepted procedure that where possible, integrals should be symbolically transformed so that any remaining singularity occurs at 0.
a language for configuring multi-level specifications. this paper shows how systems can be built from their component parts with specified sharing. its principle contribution is a modular language for configuring systems. a configuration is a description in the new language of how a system is constructed hierarchically from specifications of its component parts. category theory has been used to represent the composition of specifications that share a component part by constructing colimits of diagrams. we reformulated this application of category theory to view both configured specifications and their diagrams as algebraic presentations of presheaves. the framework of presheaves leads naturally to a configuration language that expresses structuring from instances of specifications, and also incorporates a new notion of instance reduction to extract the component instances from a particular configuration. the configuration language now expresses the hierarchical structuring of multi-level configured specifications. the syntax is simple because it is independent of any specification language; structuring a diagram to represent a configuration is simple because there is no need to calculate a colimit; and combining specifications is simple because structuring is by configuration morphisms with no need to flatten either specifications or their diagrams to calculate colimits.
computing queries with higher-order logics. in the present article, we study the expressive power of higher-order logics on finite relational structures or databases. first, we give a characterization of the expressive power of the fragments σji and πji, for each i ≥ 1 and each number of alternations of quantifier blocks j. then, we get as a corollary the expressive power of hoi for each order i ≥ 2. from our results, as well as from the results of r. hull and j. su, it turns out that no higher-order logic can be complete. even if we consider the union of higher-order logics of all natural orders, i.e., ∪i ≥ 2 hoi, we still do not get a complete logic. so, we define a logic which we call variable order logic (vo) which permits the use of untyped relation variables, i.e., variables of variable order, by allowing quantification over orders. we show that this logic is complete, though even non-recursive queries can be expressed in vo. then we define a fragment of vo and we prove that it expresses exactly the class of r.e. queries. we finally give a characterization of the class of computable queries through a fragment of vo, which is undecidable.
a practical algorithm to find the best subsequence patterns. given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. we regard it to find a subsequence pattern which separates these two sets. the problem is known to be np-complete. we naturally generalize it to an optimization problem, where we try to find a subsequence pattern which maximally separates these two sets. we provide a practical algorithm to solve it exactly. our algorithm uses two pruning heuristics based on the properties of subsequence languages, and utilizes the data structure called subsequence automata. we report some experimental results, which show these heuristics and the data structure contribute to reduce the search time.
direct and indirect algorithms for on-line learning of disjunctions. it is easy to design on-line learning algorithms for learning k out of n variable monotone disjunctions by simply keeping one weight per disjunction. such algorithms use roughly o(nk) weights which can be prohibitively expensive. surprisingly, algorithms like winnow require only n weights (one per variable or attribute) and the mistake bound of these algorithms is not too much worse than the mistake bound of the more costly algorithms. the purpose of this paper is to investigate how exponentially many weights can be collapsed into only o(n) weights. in particular, we consider probabilistic assumptions that enable the bayes optimal algorithm's posterior over the disjunctions to be encoded with only o(n) weights. this results in a new o(n) algorithm for learning disjunctions which is related to the bylander's beg algorithm originally introduced for linear regression. besides providing a bayesian interpretation for this new algorithm, we are also able to obtain mistake bounds for the noise free case resembling those that have been derived for the winnow algorithm. the same techniques used to derive this new algorithm also provide a bayesian interpretation for a normalized version of winnow.
tile invariants: new horizons. let t be a finite set of tiles. the group of invariants g(t), introduced by pak (trans. ams 352 (2000) 5525), is a group of linear relations between the number of copies of tiles in tilings of the same region. we survey known results about g, the height function approach, the local move property, various applications and special cases.
approximate algorithms for neural-bayesian approaches. we describe two specific examples of neural-bayesian approaches for complex modeling tasks: survival analysis and multitask learning. in both cases, we can come up with reasonable priors on the parameters of the neural network. as a result, the bayesian approaches improve their (maximum likelihood) frequentist counterparts dramatically. by illustrating their application on the models under study, we review and compare algorithms that can be used for bayesian inference: laplace approximation, variational algorithms, monte carlo sampling, and empirical bayes.
the dynamic complexity of transitive closure is in dyntc. this paper presents a fully dynamic algorithm for maintaining the transitive closure of a binary relation. all updates and queries can be computed by constant depth threshold circuits of polynomial size (tc0 circuits). this places dynamic transitive closure in the dynamic complexity class dyntc0, and implies that transitive closure can be maintained in database systems that include first-order update queries and aggregation operators, using a database with size polynomial in the size of the relation.
p-immune sets with holes lack self-reducibility properties. no p-immune set having exponential gaps is positive-turing self-reducible.
algebraic tools for the concatenation product. this paper is a contribution to the algebraic study of the concatenation product. in the first part of the paper, we extend to the ordered case standard algebraic tools related to the concatenation product, like the schützenberger product and the relational morphisms. we show in a precise way how the ordered schützenberger product corresponds to polynomial operations on languages. in the second part of the paper, we apply these results to establish a bridge between the three standard concatenation hierarchies, namely the straubing-thérien hierarchy, the brzozowski's (or dot-depth) hierarchy and the group hierarchy.
all superlinear inverse schemes are conp-hard. how hard is it to invert np-problems? we show that all superlinearly certified inverses of np problems are conp-hard. to do so, we develop a novel proof technique that builds diagonalizations against certificates directly into a circuit.
reducibility classes of p-selective sets. a set is p-selective if there is a polynomial-time semi-decision algorithm for the set---an algorithm that given any two strings decides which is ``more likely'''' to be in the set. this paper establishes a strict hierarchy among the various reductions and equivalences to p-selective sets.
p-selectivity: intersections and indices. the p-selective sets are those sets for which there is a polynomial-time algorithm that, given any two strings, determines which is ``more likely'''' to belong to the set: if either of the strings is in the set, the algorithm chooses one that is in the set. we prove that, for each k, the k-ary boolean connectives under which the p-selective sets are closed are exactly those that are either completely degenerate or almost-completely degenerate. we determine the complexity of the index set of the r.e. p-selective sets: \sigma_3^0-complete.
the alternating greedy expansion and applications to computing digit expansions from left-to-right in cryptography. the central topic of this paper is the alternating greedy expansion of integers, which is defined to be a binary expansion with digits {0, ±1} with the property that the nonzero digits have alternating signs. we collect known results about this alternating greedy expansion and complement it with other useful properties and algorithms. in the second part, we apply it to give an algorithm for computing a joint expansion of d integers of minimal joint hamming weight from left to right, i.e., from the column with the most significant bits towards the column with the least significant bits. furthermore, we also compute an expansion equivalent to the so-caled w-naf from left to right using the alternating greedy expansion.
electronic jury voting protocols. this work stresses the fact that all current proposals for electronic voting schemes disclose the final tally of the votes. in certain situations, like jury voting, this may be undesirable. we present a robust and universally verifiable membership testing scheme (mts) that allows, among other things, a collection of voters to cast votes and determine whether their tally belongs to some pre-specified small set (e.g., exceeds a given threshold)--our scheme discloses no additional information than that implied from the knowledge of such membership. we discuss several extensions of our basic mts. all the constructions presented combine features of two parallel lines of research concerning electronic voting schemes, those based on mix-networks and in homomorphic encryption.
testing conformance of a deterministic implementation against a non-deterministic stream x-machine. stream x-machines are a formalisation of extended finite state machines that have been used to specify systems. one of the great benefits of using stream x-machines, for the purpose of specification, is the associated test generation technique which produces a test that is guaranteed to determine correctness under certain design for test conditions. this test generation algorithm has recently been extended to the case where the specification is non-deterministic. however, the algorithms for testing from a non-deterministic stream x-machine currently have limitations: either they test for equivalence, rather than conformance or they restrict the source of nondeterminism allowed in the specification. this paper introduces a new test generation algorithm that overcomes both of these limitations, for situations where the implementation is known to be deterministic.
probabilistic quickest path algorithm. due to the increasing role of quickest paths for on-demand routing in computer networks, it is important to compute them faster, perhaps, by trading-off the quality for computational speed. we consider the computation of a quickest path from a source node to a destination node for a given message size in a network with n nodes and m links each of which is specified by bandwidth and delay. every known quickest path algorithm computes m shortest paths either directly or indirectly, and this step contributes to most of its computational complexity which is generally of the form o(m2 + mnlogn). we present a probabilistic quickest path algorithm that computes an approximate quickest path with time complexity o(pm + pn log n) by randomly selecting p ≤ m bandwidths at which the shortest paths are computed. we show that the delay of the computed path is close to optimal with a high probability that approaches 1 exponentially fast with respect to p/m. simulation results indicate that this algorithm computes the optimal quickest paths with p/m < 0.1 for almost all randomly generated networks with n > 40. we also present an algorithm to compute the path-table consisting of these approximate quickest paths with the same time complexity of o(pm + pn log n)
the complexity of kemeny elections. kemeny proposed a voting scheme which is distinguished by the fact that it is the unique voting scheme that is neutral, consistent, and condorcet. bartholdi, tovey, and trick showed that determining the winner in kemeny's system is np-hard. we provide a stronger lower bound and an upper bound matching the lower bound, namely, we show that determining the winner in kemeny's system is complete for p||np, the class of sets solvable via parallel access to np.
unavoidable sets. we obtain new results on minimum lengths of words in an unavoidable set of words of cardinality n before introducing the notion of aperiodic unavoidable sets, a natural extension of unavoidable sets.
lower bounds and the hardness of counting properties. rice's theorem states that all nontrivial language properties of recursively enumerable sets are undecidable. borchert and stephan (math. logic quart. 46 (4) (2000) 489-504) started the search for complexity-theoretic analogs of rice's theorem, and proved that every nontrivial counting property of boolean circuits is up-hard. hemaspaandra and rothe (theoret. comput. sci. 244 (1-2) (2000) 205-217) improved the up-hardness lower bound to upo(1)-hardness. the present paper raises the lower bound for nontrivial counting properties from upo(1)-hardness to fewp-hardness, i.e., from constant-ambiguity nondeterminism to polynomial-ambiguity nondeterminism. furthermore, we prove that no relativizable technique can raise this lower bound to fewp-≤1-ttp -hardness. we also prove a rice-style theorem for np, namely that every nontrivial language property of np sets is np-hard, and for a broad class of leaf-language classes we prove a sufficient condition for the natural analog of rice's theorem to hold.
a comparison of statecharts step semantics. the paper studies some variants of statecharts step semantics in the framework of structural operational semantics. the chosen framework allows to study precongruence and congruence properties of behavioral preorders and equivalences and to compare, with respect to these properties, the different step semantics considered.
optimal advice. ko [1983] proved that the p-selective sets are in the advice class p/quadratic. we prove that the p-selective sets are in np/linear \cap conp/linear. we show this to be optimal in terms of the amount of advice needed.
prediction-hardness of acyclic conjunctive queries. a conjunctive query problem is a problem to determine whether or not a tuple belongs to the answer of a conjunctive query over a database. in this paper, a tuple, a conjunctive query and a database in relational database theory are regarded as a ground atom, a nonrecursive function-free definite clause and a finite set of ground atoms, respectively, in inductive logic programming terminology. an acyclic conjunctive query problem is a conjunctive query problem with acyclicity. concerned with the acyclic conjunctive query problem, in this paper, we present the hardness results of predicting acyclic conjunctive queries from an instance with a j-database of which predicate symbol is at most j-ary. also we deal with two kinds of instances, a simple instance as a set of ground atoms and an extended instance as a set of pairs of a ground atom and a description. we mainly show that, from both a simple and an extended instances, acyclic conjunctive queries are not polynomial-time predictable with j-databases (j ≥ 3) under the cryptographic assumptions, and predicting acyclic conjunctive queries with 2-databases is as hard as predicting dnf formulas. hence, the acyclic conjunctive queries become a natural example that the equivalence between subsumption-efficiency and efficient pac-learnability from both a simple and an extended instances collapses.
effective metric spaces and representations of the reals. based on standard notions of classical recursion theory, a natural model of approximate computability for partial functions between effective metric spaces is presented. it generalizes the ko-friedman approach to computability of real functions by means of oracle turing machines, follows the main ideas of weihrauch's type 2 theory of effectivity, but it avoids the explicit use of representations. the topological arithmetical hierarchy is introduced and shown to be strict if the underlying space contains an effectively discrete sequence. the domains of computable functions are exactly the π2-sets of this hierarchy if the space admits a finitary stratification. finally, this framework is used to investigate and characterize the standard representations of the real numbers. they are just those functions from the name space onto the reals which have both computable extensions and inversions that are computable as relations.
a comparison of identification criteria for inductive inference of recursive real-valued functions. in this paper we investigate the inductive inference of recursive real-valued functions from data. a recursive real-valued function is regarded as a computable interval mapping. the learning model we consider in this paper is an extension of gold's inductive inference. we first introduce some criteria for successful inductive inference of recursive real-valued functions. then we show a recursively enumerable class of recursive real-valued functions which is not inferable in the limit. this should be an interesting contrast to the result by wiehagen (1976, elektronische informationsverarbeitung und kybernetik, vol. 12, pp. 93--99) that every recursively enumerable subset of recursive functions from n to n is consistently inferable in the limit. we also show that every recursively enumerable class of recursive real-valued functions on a fixed rational interval is consistently inferable in the limit. furthermore, we show that our consistent inductive inference coincides with the ordinary inductive inference, when we deal with recursive real-valued functions on a fixed closed rational interval. copyright 2001 elsevier science b.v. all rights reserved.
towards a behavioural theory of access and mobility control in distributed systems. we define a typed bisimulation equivalence for the language dpi, a distributed version of the π-calculus in which processes may migrate between dynamically created locations. it takes into account resource access policies, which can be implemented in dpi using a novel form of dynamic capability types. the equivalence, based on typed actions between configurations, is justified by showing that it is fully abstract with respect to a natural distributed version of a contextual equivalence.in the second part of the paper we study the effect of controlling the migration of processes. this affects the ability to perform observations at specific locations, as the observer may be denied access. we show how the typed actions can be modified to take this into account, and generalise the full-abstraction result to this more delicate scenario.