waashk/dblp huggingface dataset:
a characterization theorem for injective model classes axiomatized by general rules. we continue the work in zhu et al. [normal conditions for inference relations and injective models, theoret. comput. sci. 309 (2003) 287-311]. a class ω of strict partial order structures (posets, for short) is said to be axiomatizable if the class of all injective preferential models from ω may be characterized in terms of general rules. this paper aims to obtain some characteristics of axiomatizable classes. to do this, a monadic second-order frame language is presented. the relationship between χ0-axiomatizability and second-order definability is explored. then a notion of an admissible set is introduced. based on this notion, we show that any preferential model, which does not contain any four-node substructure, must be a reduct of some injective model. furthermore, we furnish a necessary and sufficient condition for the axiomatizability of classes of injective preferential models using general rules. finally, we show that, in some sense, the class of all posets without any four-node substructure is the largest among axiomatizable classes.
stability versus speed in a computable algebraic model. algebraic models of real computation and their induced notions of time complexity neglect stability issues of numerical algorithms. recursive analysis on the other hand appropriately describes stable numerical computations while, based on turing machines, usually lacks significant lower complexity bounds.we propose a synthesis of the two models, namely a restriction of algebraic algorithms to computable primitives. these are thus inherently stable and allow for nontrivial complexity considerations. in this model, one can prove on a sound mathematical foundation the empirically well-known observation that stability and speed may be contradictory goals in algorithm design.more precisely we show that solving the geometric point location problem among hyperplanes by means of a total computable decision tree (i.e., one behaving numerically stable for all possible input points) has in general complexity exponentially larger than when permitting the tree to be partial, that is, to diverge (behave in an instable way) on a 'small' set of arguments.the trade-off between the extremes is investigated quantitatively for the planar case. proofs involve both topological and combinatorial arguments.
computability in linear algebra. many problems in linear algebra can be solved by gaussian elimination. this famous algorithm applies to an algebraic model of real number computation where operations +, -, *, / and tests like, e.g., < and == are presumed exact. implementations of algebraic algorithms on actual digital computers often lead to numerical instabilities, thus revealing a serious discrepancy between model and reality.a different model of real number computation dating back to alan turing considers real numbers as limits of rational approximations. in that widely believed to be more realistic notion of computability, we investigate problems from linear algebra. our central results yield algorithms which in this sense • solve systems of linear equations a ċ x = b, • determine the spectral resolution of a symmetric matrix b, • and compute a linear subspace's dimension from its euclidean distance function, provided the rank of a and the number of distinct eigenvalues of b are known. without such restrictions, the first two problems are shown to be, in general, uncomputable.
time-stamps for mazurkiewicz traces. we construct a new time-stamp system for mazurkiewicz traces. we begin by constructing a sequential time-stamp system which turns out to be optimal for a certain class of time-stamps. in the next step we show that this time-stamp system can be adapted for mazurkiewicz traces, i.e. it can be used also in a distributed environment.
generalized acceptance, succinctness and supernondeterministic finite automata. we define generalized, acceptance in nondeterministic finite automata, in order to achieve more instances of succinct descriptions of regular languages in practical applications. we show that generalized acceptance enable the construction of a hierarchy of succinct nondeterministic descriptions for finite automata. the hierarchy corresponds to deterministic finite automata on level 0 and nondeterministic finite automata on level 1 by default, and we prove that the hierarchy corresponds to alternating (boolean) finite automata on level 2. we show that there exists an 2-state level 3 finite automaton with generalized acccptance, such that its equivalent minimal deterministic finite automaton has more that 222 states.
separation of uniform learning classes. within the scope of inductive inference a recursion theoretic approach is used to model learning behaviour. the fundamental model considered is gold's identification of recursive functions in the limit. modifying the corresponding definition has proposed several inference classes, which have been compared regarding the capacities of the relevant learners. the present paper is concerned with a meta-version of this learning model. given a description of a class of target functions, a uniform learner is supposed to develop a specific successful method for learning the represented class. the same modifications as in the elementary model are considered in the context of uniform learning, especially respecting identification capacities. it turns out that the former separations of inference classes are reflected on the meta-level, in particular finite classes of recursive functions--which constitute the most simple learning problems in the elementary model--are evidence of these separations.
on the topological size of p-m-complete degrees. all polynomial many-one degrees are shown to be of second baire category in the superset topology when witness functions are allowed to run in 2^{\log^hn} time, for any h. any improvement of this result for the complete p-m-degrees of re, exp or np implies p \neq np.
on the size of classes with weak membership properties. it is shown that the following classes have measure 0 in e: the class of p-selective sets, the class of p-multiselective sets, the class of cheatable sets, the class of easily countable sets, the class of easily approximable sets, the class of near-testable sets, the class of nearly near-testable sets, the class of sets that are not p-bi-immune. these are corollaries of a more general result stating that the class of sets that are p-isomorphic to p-quasi-approximable sets has measure 0 in e. by considering the recent approach of allender and strauss for measuring in subexponential classes, we obtain similar results with respect to p for classes having weak logarithmic time membership properties.
peirce's rule in natural deduction. in stark contrast to natural deduction for intuitionistic logic, natural deduction for classical logic suffers from some well-known limitations: although normalisation can be proved, the standard proof of prawitz (natural deduction. a proof theoretical study, almquist and wiksell, stockholm, 1965) is restricted to a fragment of classical predicate logic without and without due to some effects of the rule of classical negation, and a proof for classical predicate logic without and without cannot be given; the extension of prawitz' proof to a language with and due to stalmarck (j. symbolic logic 56 (1991) 129) still remaining language dependent on and . such facts raise some doubts about the proof theoretical significance of the classical negation rule, the reductio ad absurdum, introduced by prawitz. instead of this rule, peirce's rule may be chosen, a purely implicative elimination rule, proposed for classical natural deduction by curry (foundations of mathematical logic, mcgraw-hill, new york, 1963): this rule can be proved to be deductively equivalent with the classical negation rule, and this rule admits formulations of classical predicate logic without and without . in the following paper, it is shown that with peirce's rule, several theorems of weak normalisation for classical logic are provable, i.e. weak normalisation for any fragment of classical logic containing and being enriched with any of the signs and respective rules ,,,,thus the most general proofs of normalisation for classical predicate logic are given.
solving the generalized mask constraint for test generation of binary floating point add operation. the mathematical problem discussed is important for generating test cases in order to debug floating point adders designs.floating point numbers are assumed to be written as strings of {0, 1} bits, in a format compatible with ieee standard 754. a mask is a string of characters, composed of {'0', '1', 'x'}. a number and a mask are compatible if they have the same length and each numerical character of the mask ('0' or '1') is equal, numerically, to the bit of the number, in the same position. the problem discussed is: given masks ma, mb, mc, of identical lengths, generate three floating point numbers a,b,c which are compatible with the masks and satisfy c=round(a±b)). if there are many solutions, choose one at random. a fast algorithm is given which solves the problem for all ieee floating point data types and all rounding modes.
weakening the perfect encryption assumption in dolev-yao adversaries. we consider secrecy and authentication in a simple process calculus with cryptographic primitives. the standard dolev-yao adversary is enhanced so that it can guess the key required to decrypt an intercepted message. we borrow from the computational complexity approach the assumptions that guessing succeeds with a given negligible probability and that the resources available to adversaries are polynomially bounded. under these hypotheses we prove that the standard dolev-yao adversary is as powerful as the enhanced one.
satgraphs and independent domination. part 1. a graph g is called a satgraph if there exists a partition a ∪ b = v(g) such that • a induces a clique [possibly, a = 0], • b induces a matching [i.e., g(b) is a 1-regular subgraph, possibly, b = 0], and • there are no triangles (a, b, b'), where a ∈ a and b, b' ∈ b.we also introduce the hereditary closure of iaj, denoted by hiaj [hereditary satgraphs]. the class hiaj contains split graphs. in turn, hiaj is contained in the class of all (1, 2)-split graphs [a. gyárfás, generalized split graphs and ramsey numbers, j. combin. theory ser. a 81 (2) (1998) 255-261], the latter being still not characterized. we characterize satgraphs in terms of forbidden induced subgraphs.there exist close connections between satgraphs and the satisfiability problem [sat]. in fact, sat is linear-time equivalent to finding the independent domination number in the corresponding satgraph. it follows that the independent domination problem is np-complete for the hereditary satgraphs. in particular, it is np-complete for perfect graphs.
independent domination in hereditary classes. we investigate independent domination problem within hereditary classes of graphs. boliac and lozin [independent domination in finitely defined classes of graphs, theoret. comput. sci. 301 (1-3) (2003) 271-284] proved some sufficient conditions for independent domination problem to be np-complete within finitely defined hereditary classes of graphs. they posed a question whether the conditions are also necessary. we show that the conditions are not necessary, since independent domination problem is np-hard within 2p3-free graphs.moreover, we show that the problem remains np-hard for a new hereditary class of graphs, called hereditary 3-satgraphs. we characterize hereditary 3-satgraphs in terms of forbidden induced subgraph. as corollaries, we prove that independent domination problem is np-hard within the class of all 2p3-free perfect graphs and for k1,5-free weakly chordal graphs.finally, we compare complexity of independent domination problem with that of independent set problem for a hierarchy of hereditary classes recently proposed by hammer and zverovich [construction of maximal stable sets with k-extensions, combin. probab. comput. 13 (2004) 1-8]. for each class in the hierarchy, a maximum independent set can be found in polynomial time, and the hierarchy covers all graphs. however, our characterization of hereditary 3-satgraphs implies that independent domination problem is np-hard for almost all classes in the hierarchy. this fact supports a conjecture that independent domination is harder than independent set problem within hereditary classes.
the memory game. the memory game is a popular card game played by children and adults around the world. good memory is one of the qualities required in order to succeed in it. this however is not enough.when it is assumed that the players have perfect memory, the memory game can be seen as a game of strategy. the game is analysed under this assumption and the optimal strategy is found. this is simple and perhaps unexpected. in contrast to the simplicity of the optimal strategy, the analysis leading to its optimality proof is rather involved. it supplies an interesting example of concrete mathematics of the sort used in the analysis of algorithms. it is doubtful whether this analysis could have been carried out without resort to experimentation and substantial use of automated symbolic computation.
martin's game: a lower bound for the number of sets. we investigate martin's game (as described in arruda et al. (eds.), on random r. e. sets, non-classical logics, model theory and computability, north-holland, amsterdam, 1977, p. 283) and prove that the upper bound from the above mentioned reference for the number of sets needed to construct a winning strategy, is almost tight.
a genetic system based on simulated crossover of sequences of two-bit genes. we introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. results are(1)a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state); (2)states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials); (3)in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time o(m+l), where l is the chromosome length; (4)the genetic algorithm (implementing the proposed infinite population system) is experimentally compared with the infinite population genetic algorithm with bit-based simulated crossover for the max-cut problem; the results show that the extension to sequences of genes with four alleles is useful to improve performances.
global convergence of oja's pca learning algorithm with a non-zero-approaching adaptive learning rate. a non-zero-approaching adaptive learning rate is proposed to guarantee the global convergence of oja's principal component analysis (pca) learning algorithm. most of the existing adaptive learning rates for oja's pca learning algorithm are required to approach zero as the learning step increases. however, this is not practical in many applications due to the computational round-off limitations and tracking requirements. the proposed adaptive learning rate overcomes this shortcoming. the learning rate converges to a positive constant, thus it increases the evolution rate as the learning step increases. this is different from learning rates which approach zero which slow the convergence considerably and increasingly with time. rigorous mathematical proofs for global convergence of oja's algorithm with the proposed learning rate are given in detail via studying the convergence of an equivalent deterministic discrete time (ddt) system. extensive simulations are carried out to illustrate and verify the theory derived. simulation results show that this adaptive learning rate is more suitable for oja's pca algorithm to be used in an online learning situation.
chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment. modern cryptography is based on various building blocks such as one way functions with or without trapdoors, pseudo-random functions, one way permutations with or without trapdoors, etc. in a quantum world some of the main candidates for these building blocks are broken. for instance, the security of the most popular public-key cryptosystem-rsa-is related to the difficulty of factoring large numbers, and is broken (in principle) by a quantum computer. we investigate some of the remaining candidates, and discuss the resulting ''post-quantum cryptography'' (namely, the resulting ''modern cryptography in a quantum environment''). about half a decade ago ajtai and dwork (and later on, also goldreich, goldwasser and halevi) proposed a public key cryptosystem that has a proven security under a plausible complexity assumption. the plausible assumption is that the so-called unique shortest vector problem (u-svp) is hard on the worst case. this problem is potentially still hard also in a quantum environment. recently, regev introduced a new (and much simpler) public key cryptosystem, based on the same u-svp hardness assumption, but with improved parameters. in this paper we present chosen ciphertext attacks (cca) against all three cryptosystems. our attack shows that these cryptosystems are totally insecure against cca, because the private keys can be recovered in polynomial time. we then discuss the possibility of making public key encryption (pke) secure against cca, without adding stronger assumptions than the assumption that u-svp is hard. we conclude that the current understanding of modern cryptography in a quantum environment can only suggest cca-secure interactive-pke, which is obviously weaker than cca-secure pke. finally, we discuss the relation of our attack to the reaction attack of hall, goldberg and schneier, which we only recently became aware of.
rewriting queries using views in the presence of arithmetic comparisons. we consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons over dense orders. previous work only considered limited variants of this problem, without giving a complete solution. we first show that obtaining equivalent rewritings for conjunctive queries with arithmetic comparisons is decidable. then, we consider the problem of finding maximally contained rewritings (mcrs) where the decidability proof does not carry over. we investigate two special cases of this problem where the query uses only semi-interval comparisons. in both cases decidability of finding mcrs depends on the query containment test. first, we address the case where the homomorphism property holds in testing query containment. in this case decidability is easy to prove but developing an efficient algorithm is not trivial. we develop such an algorithm and prove that it is sound and complete. this algorithm applies in many cases where the query uses only left (or right) semi-interval comparisons. then, we develop a new query containment test for the case where the containing query uses both left and right semi-interval comparisons but with only one left (or right) semi-interval subgoal. based on this test, we show how to produce an mcr which is a datalog query with arithmetic comparisons. the containment test that we develop obtains a result of independent interest. it finds another special case where query containment in the presence of arithmetic comparisons can be tested in nondeterministic polynomial time.
a formal fuzzy reasoning system and reasoning mechanism based on propositional modal logic. we establish in this paper a fuzzy propositional modal logic, fpml, and the associated semantics, fuzzy kripke semantics. we prove that fpml is sound and complete. furthermore, we set up a formalized reasoning mechanism based on fpml.
a flexible model for dynamic linking in java and c#. dynamic linking supports flexible code deployment, allowing partially linked code to link further code on the fly, as needed. thus, end-users enjoy the advantage of automatically receiving any updates, without any need for any explicit actions on their side, such as re-compilation, or re-linking. on the down side, two executions of a program may link in different versions of code, which in some cases causes subtle errors, and may mystify end-users. dynamic linking in java and c# are similar: the same linking phases are involved, soundness is based on similar ideas, and executions which do not throw linking errors give the same result. they are, however, not identical: the linking phases are combined differently, and take place in different order. consequently, linking errors may be detected at different times by java and c# runtime systems. we develop a non-deterministic model, which describes the behaviour of both java and c# program executions. the non-determinism allows us to describe the design space, to distill the similarities between the two languages, and to use one proof of soundness for both. we also prove that all execution strategies are equivalent with respect to terminating executions that do not throw link errors: they give the same results.
a simple optimal representation for balanced parentheses. we consider succinct, or highly space-efficient, representations of a (static) string consisting of n pairs of balanced parentheses, which support natural operations such as finding the matching parenthesis for a given parenthesis, or finding the pair of parentheses that most tightly enclose a given pair. this problem was considered by jacobson [space-efficient static trees and graphs, in: proc. of the 30th focs, 1989, pp. 549-554] and munro and raman [succinct representation of balanced parentheses and static trees, siam j. comput. 31 (2001) 762-776] who gave o(n)-bit and 2n+o(n)-bit representations, respectively, that supported the above operations in o(1) time on the ram model of computation. this data structure is a fundamental tool in succinct representations, and has applications in representing suffix trees, ordinal trees, planar graphs and permutations. we consider the practical performance of parenthesis representations. first, we give a new 2n+o(n)-bit representation that supports all the above operations in o(1) time. this representation is conceptually simpler, its space bound has a smaller o(n) term and it also has a simple and uniform o(n) time and space construction algorithm. we implement our data structure and a variant of jacobson's, and evaluate their practical performance (speed and memory usage), when used in a succinct representation of trees derived from xml documents. as a baseline, we compare our representations against a widely used implementation of the standard dom (document object model) representation of xml documents. both succinct representations use orders of magnitude less space than dom and tree traversal operations are usually only slightly slower than in dom.
type checking a multithreaded functional language with session types. we define a language whose type system, incorporating session types, allows complex protocols to be specified by types and verified by static type checking. a session type, associated with a communication channel, specifies the state transitions of a protocol and also the data types of messages associated with transitions; thus type checking can verify both correctness of individual messages and correctness of sequences of transitions. previously, session types have mainly been studied in the context of the @p-calculus; instead, our formulation is based on a multithreaded functional language with side-effecting input/output operations. our typing judgements statically describe dynamic changes in the types of channels, and our function types not only specify argument and result types but also describe changes in channels. we formalize the syntax, semantics and type checking system of our language, and prove subject reduction and runtime type safety theorems.