waashk/dblp huggingface dataset:
optimal semi-online algorithms for machine covering. this paper investigates the semi-online machine covering problems on m>=3 parallel identical machines. three different semi-online versions are studied and optimal algorithms are proposed. we prove that if the total processing time of all jobs or the largest processing time of all jobs is known in advance, the competitive ratios of the optimal algorithms are both m-1. if the total processing time and the largest processing time of all jobs are both known in advance, the competitive ratios of the optimal algorithms are 32 when m=3, and m-2 when m>=4.
on the membership of invertible diagonal and scalar matrices. in this paper, we consider decidability questions that are related to the membership problem in matrix semigroups. in particular, we consider the membership of a given invertible diagonal matrix in a matrix semigroup and then a scalar matrix, which has a separate geometric interpretation. both problems have been open for any dimensions and are shown to be undecidable in dimension 4 with integral matrices by a reduction of the post correspondence problem (pcp). although the idea of pcp reduction is standard for such problems, we suggest a new coding technique to cover the case of diagonal matrices.
multiset random context grammars, checkers, and transducers. we introduce a general model of random context multiset grammars as well as the concept of multiset random context checkers and transducers. our main results show how recursively enumerable sets of finite multisets can be generated using these models of computing; corresponding results for antiport p systems are established, too.
three "quantum" algorithms to solve 3-sat. in this paper we borrow some ideas from quantum computing, and we propose three ''quantum'' brute force algorithms to solve the 3-sat np-complete decision problem. the first algorithm builds, for any instance @f of 3-sat, a quantum fredkin circuit that computes a superposition of all classical evaluations of @f in a given output line. similarly, the second and third algorithms compute the same superposition on a given register of a quantum register machine, and as the energy of a given membrane in a quantum p system, respectively. assuming that a specific non-unitary operator, built using a truncated version of the well known creation and annihilation operators, can be realized as a quantum gate, as an instruction of the quantum register machine, and as a rule of the quantum p system, respectively, we show how to decide whether @f is a positive instance of 3-sat. the construction relies also upon the assumption that an external observer is able to discriminate, as the result of a measurement, a null vector from a non-null vector.
minimum cost source location problem with local 3-vertex-connectivity requirements. let g=(v,e) be a simple undirected graph with a set v of vertices and a set e of edges. each vertex v@?v has a demand d(v)@?z"+ and a cost c(v)@?r"+, where z"+ and r"+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. the source location problem with vertex-connectivity requirements in a given graph g requires finding a set s of vertices minimizing @?"v"@?"sc(v) such that there are at least d(v) pairwise vertex-disjoint paths from s to v for each vertex v@?v-s. it is known that if there exists a vertex v@?v with d(v)>=4, then the problem is np-hard even in the case where every vertex has a uniform cost. in this paper, we show that the problem can be solved in o(|v|^4log^2|v|) time if d(v)@?3 holds for each vertex v@?v.
normal forms for spiking neural p systems. the spiking neural p systems are a class of computing devices recently introduced as a bridge between spiking neural nets and membrane computing. in this paper we prove a series of normal forms for spiking neural p systems, concerning the regular expressions used in the firing rules, the delay between firing and spiking, the forgetting rules used, and the outdegree of the graph of synapses. in all cases, surprising simplifications are found, without losing the computational completeness - sometimes at the price of (slightly) increasing other parameters which describe the complexity of these systems.
cycles and communicating classes in membrane systems and molecular dynamics. we are considering sequential membrane systems and molecular dynamics from the viewpoint of markov chain theory. the configuration space of these systems (including the transitions) is a special kind of directed graph, called a pseudo-lattice digraph, which is closely related to the stoichiometric matrix. taking advantage of the monoidal structure of this space, we introduce the algebraic notion of precycle. a precycle leads to the identification of cycles by means of the concept of defect, which is a set of geometric constraints on configuration space. two efficient algorithms for evaluating precycles and defects are given: one is an algorithm due to contejean and devie, the other is a novel branch-and-bound tree search procedure. cycles partition configuration space into equivalence classes, called the communicating classes. the structure of the communicating classes in the free regime-where all rules are enabled-is analyzed: testing for communication can be done efficiently. we show how to apply these ideas to a biological regulatory system.
on small universal antiport p systems. it is known that p systems with antiport rules simulate register machines, i.e., they are computationally complete. hence, due to the existence of universal register machines, there exist computationally complete subclasses of antiport p systems with bounded size, i.e., systems where each size parameter is limited by some constant. however, so far there has been no estimation of these numbers given in the literature. in this article, three universal antiport p systems of bounded size are demonstrated, different from each other in their size parameters. we present universal antiport p systems with 73, 43, and 30 rules where the maximum of the weight of the rules is 4, 5, and 6, respectively.
optimal trade-off for merkle tree traversal. in this paper we describe optimal trade-offs between time and space complexity of merkle tree traversals with their associated authentication paths, improving on the previous results of m. jakobsson, t. leighton, s. micali, and m. szydlo [fractal merkle tree representation and traversal, in: rsa cryptographers track, rsa security conference, 2003] and m. szydlo [merkle tree traversal in log space and time, in: proc. eurocrypt, in: lncs, vol. 3027, 2004, pp. 541-554; merkle tree traversal in log space and time, preprint version 2003, available at http://www.szydlo.com]. in particular, we show that our algorithm requires 2logn/log^(^3^)n hash function computations and storage for less than (logn/log^(^3^)n+1)loglogn+2logn hash values, where n is the number of leaves in the merkle tree. we also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than o(logn/logt) time and less than o(tlogn/logt) space for any choice of parameter t>=2. our algorithm could be of special interest in the case when both time and space are limited.
reallife: the continuum limit of larger than life cellular automata. let a@?{0,1}. a cellular automaton (ca) is a shift-commuting transformation of a^z^^^d determined by a local rule. likewise, a euclidean automaton (ea) is a shift-commuting transformation of a^r^^^d determined by a local rule. larger than life (ltl) ca are long-range generalizations of j.h. conway's game of life ca, proposed by k.m. evans. we prove a conjecture of evans: as their radius grows to infinity, ltl ca converge to a 'continuum limit' ea, which we call reallife. we also show that the life forms (fixed points, periodic orbits, and propagating structures) of ltl ca converge to life forms of reallife. finally we prove a number of existence results for fixed points of reallife.
discrete solutions to differential equations by metabolic p systems. the relationships existing between metabolic p systems and ode systems are investigated. formal results show that every mp system determines a structure, called an mp graph, which results in an ode system whose solution equals, in the limit, the evolution of any non-cooperative mp system that can be derived from the initial one by means of a systematic procedure. examples based on the model of a mitotic oscillator in early amphibian embryos, the lotka-volterra predator-prey population dynamics, and the lorenz strange attractor are provided, showing the applicability of the proposed computational approach.
an efficient identity-based key exchange protocol with kgs forward secrecy for low-power devices. for an id-based key exchange (ke) protocol, kgs forward secrecy is about the protection of previously established session keys after the master secret key of the key generation server (kgs) is compromised. this is the strongest notion of forward secrecy that one can provide for an id-based ke protocol. among all the comparable protocols, there are only a few of them that provide this level of forward secrecy, and all of these protocols require expensive bilinear pairing operations and map-to-point hash operations that may not be suitable for implementation on low-power devices such as sensors. in this paper, we propose a new id-based ke protocol which does not need any pairing or map-to-point hash operations. it also supports the strongest kgs forward secrecy. on its performance, we show that it is faster than previously proposed protocols in this category. our protocol is a signature-based one, in which the signature scheme is a variant of a scheme proposed by bellare et al. in eurocrypt 2004. we show that the variant we proposed is secure, and also requires either less storage space or runtime computation than the original scheme.
smoothed analysis of binary search trees. binary search trees are one of the most fundamental data structures. while the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. the exact value is one of the best studied problems in average-case complexity. we investigate what happens in between by analysing the smoothed height of binary search trees: randomly perturb a given (adversarial) sequence and then take the expected height of the binary search tree generated by the resulting sequence. as perturbation models, we consider partial permutations, partial alterations, and partial deletions. on the one hand, we prove tight lower and upper bounds of roughly @q((1-p)@?n/p) for the expected height of binary search trees under partial permutations and partial alterations, where n is the number of elements and p is the smoothing parameter. this means that worst-case instances are rare and disappear under slight perturbations. on the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse well balanced instances can become.
on the degree of parallelism in membrane systems. in the literature, several designs of p systems might be found for performing the same task. the use of different techniques or even different p system models makes it very difficult to compare these designs. in this paper, we introduce a new criterion for such a comparison: the degree of parallelism of a p system. with this aim, we define the labelled dependency graph associated with a p system, and we use this new concept for proving some results concerning the maximum number of applications of rules in a single step through the computation of a p system.
learning of erasing primitive formal systems from positive examples. the present paper considers the learning problem of erasing primitive formal systems, pfss for short, in view of inductive inference in gold framework from positive examples. a pfs is a kind of logic program over strings called regular patterns, and consists of exactly two axioms of the forms p(π) ← and p(τ) ← p(x1),..., p(xn), where p is a unary predicate symbol, π and τ are regular patterns, and xis are distinct variables. a pfs is erasing or nonerasing according to allowing the empty string substitution for some variables or not. we investigate the learnability of the class pfsl of languages generated by the erasing pfss satisfying a certain condition. we first show that the class pfsl has m-finite thickness. moriyama and sato showed that a language class with m-finite thickness is learnable if and only if there is a finite tell tale set for each language in the class. we then introduce a particular type of finite set of strings for each erasing pfs, and show that the set is a finite tell tale set of the language. these imply that the class pfsl is learnable from positive examples.
from learning in the limit to stochastic finite learning. inductive inference can be considered as one of the fundamental paradigms of algorithmic learning theory. we survey results recently obtained and show their impact to potential applications.since the main focus is put on the efficiency of learning, we also deal with postulates of naturalness and their impact to the efficiency of limit learners. in particular, we look at the learnability of the class of all pattern languages and ask whether or not one can design a learner within the paradigm of learning in the limit that is nevertheless efficient.for achieving this goal, we deal with iterative learning and its interplay with the hypothesis spaces allowed. this interplay has also a severe impact to postulates of naturalness satisfiable by any learner.furthermore, since a limit learner is only supposed to converge, one never knows at any particular learning stage whether or not the learner did already succeed. the resulting uncertainty may be prohibitive in many applications. we survey results to resolve this problem by outlining a new learning model, called stochastic finite learning. though pattern languages can neither be finitely inferred from positive data nor pac-learned, our approach can be extended to a stochastic finite learner that exactly infers all pattern languages from positive data with high confidence.finally, we apply the techniques developed to the problem of learning conjunctive concepts.
on generalized computable universal priors and their convergence. solomonoff unified occam's razor and epicurus' principle of multiple explanations to one elegant, formal, universal theory of inductive inference, which initiated the field of algorithmic information theory. his central result is that the posterior of the universal semimeasure m converges rapidly to the true sequence generating posterior µ, if the latter is computable. hence, m is eligible as a universal predictor in case of unknown µ. the first part of the paper investigates the existence and convergence of computable universal (semi) measures for a hierarchy of computability classes: recursive, estimable, enumerable, and approximable. for instance, m is known to be enumerable, but not estimable, and to dominate all enumerable semimeasures. we present proofs for discrete and continuous semimeasures. the second part investigates more closely the types of convergence, possibly implied by universality: in difference and in ratio, with probability 1, in mean sum, and for martin-löf random sequences. we introduce a generalized concept of randomness for individual sequences and use it to exhibit difficulties regarding these issues. in particular, we show that convergence fails (holds) on generalized-random sequences in gappy (dense) bernoulli classes.
an approach to intrinsic complexity of uniform learning. inductive inference is concerned with algorithmic learning of recursive functions. in the model of learning in the limit a learner successful for a class of recursive functions must eventually find a program for any function in the class from a gradually growing sequence of its values. this approach is generalised in uniform learning, where the problem of synthesising a successful learner for a class of functions from a description of this class is considered.a common reduction-based approach for comparing the complexity of learning problems in inductive inference is intrinsic complexity. informally, if a learning problem (a class of recursive functions) a is reducible to a learning problem (a class of recursive functions) b, then a solution for b can be transformed into a solution for a. in the context of intrinsic complexity, reducibility between two classes is expressed via recursive operators transforming target functions in one direction and sequences of corresponding hypotheses in the other direction.the present paper is concerned with intrinsic complexity of uniform learning. the relevant notions are adapted and illustrated by several examples. characterisations of complete classes finally allow for various insightful conclusions. the connection to intrinsic complexity of non-uniform learning is revealed within several analogies concerning first the structure of complete classes and second the general interpretation of the notion of intrinsic complexity.
learning a subclass of regular patterns in polynomial time. an algorithm for learning a subclass of erasing regular pattern languages is presented. on extended regular pattern languages generated by patterns π of the form x0α1x1... αmxm, where x0,..., xm are variables and α1,..., αm strings of terminals of length c each, it runs with arbitrarily high probability of success using a number of examples polynomial in m (and exponential in c). it is assumed that m is unknown, but c is known and that samples are randomly drawn according to some distribution, for which we only require that it has certain natural and plausible properties.aiming to improve this algorithm further we also explore computer simulations of a heuristic.
signal extraction and knowledge discovery based on statistical modeling. in the coming post it era, the problems of signal extraction and knowledge discovery from huge data sets will become very important. for these problems, the use of good model is crucial and thus the statistical modeling will play an important role. in this paper, we show two basic tools for statistical modeling, namely the information criteria for the evaluation of the statistical models and generic state-space model which provides us with a very flexible tool for modeling complex and time-varying systems. as examples of these methods we shall show some applications in seismology and macro economics.
on ordinal vc-dimension and some notions of complexity. we generalize the classical notion of vapnik-chernovenkis (vc) dimension to ordinal vc-dimension, in the context of logical learning paradigms. logical learning paradigms encompass the numerical learning paradigms commonly studied in inductive inference. a logical learning paradigm is defined as a set w of structures over some vocabulary, and a set d of first-order formulas that represent data. the sets of models of ϕ in w, where ϕ varies over d, generate a natural topology w over w.we show that if d is closed under boolean operators, then the notion of ordinal vc-dimension offers a perfect characterization for the problem of predicting the truth of the members of d in a member of w, with an ordinal bound on the number of mistakes. this shows that the notion of vc-dimension has a natural interpretation in inductive inference, when cast into a logical setting. we also study the relationships between predictive complexity, selective complexity--a variation on predictive complexity--and mind change complexity. the assumptions that d is closed under boolean operators and that w is compact often play a crucial role to establish connections between these concepts.we then consider a computable setting with effective versions of the complexity measures, and show that the equivalence between ordinal vc-dimension and predictive complexity fails. more precisely, we prove that the effective ordinal vc-dimension of a paradigm can be defined when all other effective notions of complexity are undefined. on a better note, when w is compact, all effective notions of complexity are defined, though they are not related as in the noncomputable version of the framework.
well-calibrated predictions from on-line compression models. it has been shown recently that transductive confidence machine (tcm) is automatically well-calibrated when used in the on-line mode and provided that the data sequence is generated by an exchangeable distribution. in this paper we strengthen this result by relaxing the assumption of exchangeability of the data-generating distribution to the much weaker assumption that the data agrees with a given "on-line compression model".
criterion of calibration for transductive confidence machine with limited feedback. this paper is concerned with the problem of on-line prediction in the situation where some data are unlabelled and can never be used for prediction, and even when the data are labelled, the labels may arrive with a delay. we construct a modification of randomised transductive confidence machine for this case and prove a necessary and sufficient condition for its predictions being calibrated, in the sense that in the long run they are wrong with a prespecified probability under the assumption that the data are generated independently by the same distribution. the condition for calibration turns out to be very weak: feedback should be given on more than a logarithmic fraction of steps.
conjunction on processes: full abstraction via ready-tree semantics. a key problem in mixing operational (e.g. process-algebraic) and declarative (e.g. logical) styles of specification is how to deal with inconsistencies arising when composing processes under conjunction. this article introduces a conjunction operator on labelled transition systems capturing the basic intuition of 'a and b = false', and considers a naive preorder that demands that an inconsistent specification can only be refined by an inconsistent implementation. the main body of the article is concerned with characterizing the largest precongruence contained in the naive preorder. this characterization will be based on what we call ready-tree semantics, which is a variant of path-based possible-worlds semantics. we prove that the induced ready-tree preorder is compositional and fully abstract, and that the conjunction operator indeed reflects conjunction. the article's results provide a foundation for, and an important step towards a unified framework that allows one to freely mix operators from process algebras and linear-time temporal logics.
towards "dynamic domains": totally continuous cocomplete -categories. it is common practice in both theoretical computer science and theoretical physics to describe the (static) logic of a system by means of a complete lattice. when formalizing the dynamics of such a system, the updates of that system organize themselves quite naturally in a quantale, or more generally, a quantaloid. in fact, we are led to consider cocomplete quantaloid-enriched categories as a fundamental mathematical structure for a dynamic logic common to both computer science and physics. here we explain the theory of totally continuous cocomplete categories as a generalization of the well-known theory of totally continuous suplattices. that is to say, we undertake some first steps towards a theory of ''dynamic domains''.
reflection in membership equational logic, many-sorted equational logic, horn logic with equality, and rewriting logic. we show that the generalized variant of formal systems where the underlying equational specifications are membership equational theories, and where the rules are conditional and can have equations, memberships and rewrites in the conditions is reflective. we also show that membership equational logic, many-sorted equational logic, and horn logic with equality are likewise reflective. these results provide logical foundations for reflective languages and tools based on these logics.