waashk/dblp huggingface dataset:
polynomial-time identification of very simple grammars from positive data. this paper concerns a subclass of simple deterministic grammars, called very simple grammars, and studies the problem of identifying the subclass in the limit from positive data. the class of very simple languages forms a proper subclass of simple deterministic languages and is incomparable to the class of regular languages. this class of languages is also known as the class of left szilard languages of context-free grammars.after providing some properties of very simple languages, we show that the class of very simple grammars is polynomial-time identifiable in the limit from positive data in the following sense. that is, we show that there effectively exists an algorithm that, given a target very simple grammar g* over alphabet σ, identifies a very simple grammar g equivalent to g* in the limit from positive data, satisfying the property that the time for updating a conjecture is bounded by o(m), and the total number of prediction errors made by the algorithm is bounded by o(n), where n is the size of g*, m = max{n|σ|+1, |σ|3} and n is the total length of all positive data provided.
graphical condensation of plane graphs: a combinatorial approach. the method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by propp [generalized domino-shuffling, theoret. comput. sci. 303 (2003) 267-301], and was generalized by kuo [applications of graphical condensation for enumerating matchings and tilings, theoret. comput. sci. 319 (2004) 29-57] and yah and zhang [graphical condensation for enumerating perfect matchings, j. combin. theory ser. a 110 (2005) 113-125]. in this paper, by a purely combinatorial method some explicit identities on graphical vertex-condensation for enumerating perfect matchings of plane graphs (which do not need to be bipartite) are obtained. as applications of our results, some results on graphical edge-condensation for enumerating perfect matchings are proved, and we count the sum of weights of perfect matchings of weighted aztec diamond.
encoding types in ml-like languages. this article presents several general approaches to programming with type-indexed families of values within a hindley-milner type system. a type-indexed family of values is a function that maps a family of types to a family of values. the function performs a case analysis on the input types and returns values of possibly different types. such a case analysis on types seems to be prohibited by the hindley-milner type system. our approaches solve the problem by using type encodings. the compile-time types of the type encodings reflect the types themselves, thereby making the approaches type-safe, in the sense that the underlying type system statically prevents any mismatch between the input type and the function arguments that depend on this type.a type encoding could be either value-dependent, meaning that the type encoding is tied to a specific type-indexed family, or value-independent, meaning that the type encoding can be shared by various type-indexed families. our first approach is value-dependent: we simply interpret a type as its corresponding value. our second approach provides value-independent type encodings through embedding and projection functions; they are universal type interpretations, in that they can be used to compute other type interpretations. we also present an alternative approach to value-independent type encodings, using higher-order functors.we demonstrate our techniques through applications such as c printf-like formatting, type-directed partial evaluation, and subtype coercions.
synthesis of multi-qudit hybrid and d-valued quantum logic circuits by decomposition. recent research in generalizing quantum computation from 2-valued qudits to d-valued qudits has shown practical advantages for scaling up a quantum computer. a further generalization leads to quantum computing with hybrid qudits where two or more qudits have different finite dimensions. advantages of hybrid and d-valued gates (circuits) and their physical realizations have been studied in detail by muthukrishnan and stroud [multi-valued logic gates for quantum computation, phys. rev. a 62 (2000) 052309. [10]], daboul et al. [quantum gates on hybrid qudits, j. phys. a math. gen. 36 (2003) 2525-2536. [5]], and bartlett et al. [quantum encodings in spin systems and harmonic oscillators, phys. rev. a 65 (2002) 052316. [17]]. in both cases, a quantum computation is performed when a unitary evolution operator, acting as a quantum logic gate, transforms the state of qudits in a quantum system. unitary operators can be represented by square unitary matrices. if the system consists of a single qudit, then tilma et al. [generalized euler angle parameterization for su(n), j. phys. a math. gen. 35 (2002) 10467-10501. [15]] have shown that the unitary evolution matrix (gate) can be synthesized in terms of its euler angle parametrization. however, if the quantum system consists of multiple qudits, then a gate may be synthesized by matrix decomposition techniques such as qr factorization and the cosine-sine decomposition (csd). in this article, we present a csd based synthesis method for n qudit hybrid quantum gates, and as a consequence, derive a csd based synthesis method for n qudit gates where all the qudits have the same dimension.
computational aspects of mining maximal frequent patterns. in this paper we study the complexity-theoretic aspects of mining maximal frequent patterns, from the perspective of counting the number of all distinct solutions. we present the first formal proof that the problem of counting the number of maximal frequent itemsets in a database of transactions, given an arbitrary support threshold, is #p-complete, thereby providing theoretical evidence that the problem of mining maximal frequent itemsets is np-hard. we also extend our complexity analysis to other similar data mining problems that deal with complex data structures, such as sequences, trees, and graphs. we investigate several variants of these mining problems in which the patterns of interest are subsequences, subtrees, or subgraphs, and show that the associated problems of counting the number of maximal frequent patterns are all either #p-complete or #p-hard.
jordan curves with polynomial inverse moduli of continuity. computational complexity of two-dimensional domains whose boundaries are polynomial-time computable jordan curves with polynomial inverse moduli of continuity is studied. it is shown that the membership problem of such a domain can be solved in p^n^p, i.e., in polynomial time relative to an oracle in np, in contrast to the higher upper bound p^m^p for domains without the property of polynomial inverse modulus of continuity. on the other hand, the lower bound of up for the membership problem still holds for domains with polynomial inverse moduli of continuity. it is also shown that the shortest path problem of such a domain can be solved in pspace, close to its known lower bound, while no fixed upper bound was known for domains without this property.
on linear complexity of sequences over (2). in this paper, we consider some aspects related to determining the linear complexity of sequences over gf(2n). in particular, we study the effect of changing the finite field basis on the minimal polynomials, and thus on the linear complexity, of sequences defined over gf(2n) but given in their binary representation. let a = {ai} be a sequence over gf(2n). then ai can be represented by ai =σj=0n-1 aijαj,aij ∈ gf(2), where α is the root of the irreducible polynomial defining the field. consider the sequence b = {bi} whose elements are obtained from the same binary representation of a but assuming a different set of basis (say {γ0, γ1,..., γn-1}), i.e. bi = σj=0r-1 aijγj, we study the relation between the minimal polynomial of a and b.
the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. in this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. we show that this problem is strongly np-hard, and give an o(n(n/m+1)m) time dynamic programming algorithm and an o(mkk-1p2k-1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and p is the sum of the processing times of all families. we further give a heuristic with a performance ratio 2. we also give a polynomial-time approximation scheme for the problem.
probability distribution for simple tautologies. in this paper we investigate the size of the fraction of tautologies of the given length n against the number of all formulas of length n for implicational logic. we are specially interested in asymptotic behavior of this fraction. we demonstrate the relation between a number of premises of implicational formula and asymptotic probability of finding formula with this number of premises. furthermore, we investigate the distribution of this asymptotic probabilities. distribution for all formulas is contrasted with the same distribution for tautologies only. we prove those distributions to be so different that enable us to estimate likelihood of truth for a given long formula. despite the fact that all discussed problems and methods in this paper are solved by mathematical means, the paper may have some philosophical impact on the understanding how much the phenomenon of truth is sporadic or frequent in random logical sentences.
on the power of ambainis lower bounds. the polynomial method and the ambainis lower bound (or alb, for short) method are two main quantum lower bound techniques. while recently ambainis showed that the polynomial method is not tight, the present paper aims at studying the power and limitation of alb's. we first use known alb's to derive ω(n1.5) lower bounds for bipartiteness, bipartiteness matching and graph matching, in which the lower bound for bipartiteness improves the previous ω(n) one. we then show that all the three known ambainis lower bounds have a limitation √n min{c0(f), c1(f)}, where c0(f) and c1(f) are the 0- and 1-certificate complexities, respectively. this implies that for many problems such as triangle, k-clique, bipartiteness and bipartite/graph matching which draw wide interest and whose quantum query complexities are still open, the best known lower bounds cannot be further improved by using ambainis techniques. another consequence is that all the ambainis lower bounds are not tight. for total functions, this upper bound for alb's can be further improved to min{√c0(f)c1(f), √nċci(f)}, where ci(f) is the size of max intersection of a 0- and a 1-certificate set. again this implies that alb's cannot improve the best known lower bound for some specific problems such as and-or tree, whose precise quantum query complexity is still open. finally, we generalize the three known alb's and give a new alb style lower bound method, which may be easier to use for some problems.
structure of proofs and the complexity of cut elimination. the importance of the structure of cut-formulas with respect to proof length and proof depth has been studied in various occasions. it has been illustrated that a quantifier may be more powerful than a binary connective in cut-formulas with respect to the reduction (or increase) of proof length and proof depth, and a sequence of quantifiers of the same type (existential or universal) may be less powerful than a sequence of quantifiers of alternating types. this paper provides a refined view on cut-elimination through an analysis of the structure of proofs, brings new insight into the relation between cut-formulas and short proofs, and illustrates that a mixture of quantifiers and binary connectives could be important for achieving the maximal benefit of cut-formulas for obtaining short proofs.
approximating the minimum weight weak vertex cover. accurate network flow measurement is important for a variety of network applications, where the "flow" over an edge in the network is intuitively the rate of data traffic. the problem of efficiently monitoring the network flow can be regarded as finding the minimum weight weak vertex cover for a given graph. in this paper, we present a (2 - 2/v(g)-approximation algorithm solving for this problem, which improves previous results, where v(g) is the cyclomatic number of g.
probabilistic rebound turing machines. this paper introduces a probabilistic rebound turing machine (prtm), and investigates the fundamental property of the machine. we first prove a sublogarithmic lower space bound on the space complexity of this model with bounded errors for recognizing specific languages. this lower bound strengthens a previous lower bound for conventional probabilistic turing machines with bounded errors. we then show, by using our lower space bound and an idea in the proof of it, that i) [prtm(o(logn))] is incomparable with the class of context-free languages, ii) there is a language accepted by a two-way deterministic one counter automaton, but not in [prtm(o(logn))], and where [prtm(o(logn))] denotes the class of languages recognized by o(logn) space-bounded prtms with error probability less than . furthermore, we show that there is an infinite space hierarchy for [prtm(o(logn))]. we finally show that [prtm(o(logn))] is not closed under concatenation, kleene +, and length-preserving homomorphism. this paper answers two open problems in a previous paper.
reasoning with power defaults. this paper introduces power default reasoning (pdr), a framework for non-monotonic reasoning based on the domain-theoretic idea of modeling default rules with partial-information in a higher-order setting. pdr lifts a non-monotonic operator at the base (syntactic) level to a well-behaved, almost monotonic operator in the higher-order space of the smyth power-domain --effectively a space of sets of models. working in the model space allows us to prove the dichotomy theorem and the extension splitting theorem, leading to a more well-behaved logic and (modulo the usual complexity conjectures) a less complex logic than standard default logic. specifically, we prove that skeptical normal default inference is a problem complete for co-np(3) in the boolean hierarchy for strict propositional logic and np(4)-complete in general. these results (by changing the underlying semantics) contrasts favorably with similar results of gottlob (j. logic comput. 2(3) (1992) 397-425), who proves that standard skeptical default reasoning is π2p-complete. furthermore, we show that the skeptical non-monotonic consequence relation, defined using our domain-theoretic semantics, obeys all of the laws for preferential consequence relations defined by kraus, lehmann, and magidor. in particular, we get the property of being able to reason by cases, and the so-called law of cautious monotony. both of these laws fail for the standard propositional default logic of reiter (artificial intelligence 13 (1980) 81-132), but hold in pdr as a consequence of the dichotomy theorem and the extension splitting theorem.
completion of codes with finite bi-decoding delays. let a* be a free monoid generated by a set a and let x ⊆ a* be a code with property p. the embedding of x into a complete code y ⊆ a* with the same property p is called the completion of x. the method of completion of rational bifix codes and codes with finite decoding delays have been investigated by a number of authors. in this paper, we provide a general method of construction for completing the codes with finite bi-decoding delays. as a consequence, the completion method of rational bifix codes and codes with finite decoding delays is extended and applied to codes with finite bi-decoding delays.
security analysis of a password-based authentication protocol proposed to ieee 1363. in recent years, several protocols for password-based authenticated key exchange have been proposed. these protocols aim to be secure even though the sample space of passwords may be small enough to be enumerated by an off-line adversary. in eurocrypt 2000, bellare, pointcheval and rogaway (bpr) presented a model and security definition for authenticated key exchange. they claimed that in the ideal-cipher model (random oracles), the two-flow protocol at the core of encrypted key exchange (eke) is secure. bellare and rogaway suggested several instantiations of the ideal cipher in their proposal to the ieee p1363.2 working group. since then there has been an increased interest in proving the security of password-based protocols in the ideal-cipher model. for example, bresson, chevassut, and pointcheval have recently showed that the one-encryption-key-exchange (oeke) protocol is secure in the ideal cipher model. in this paper, we present examples of real (not ideal) ciphers (including naive implementations of the instantiations proposed to ieee p1363.2) that would result in broken instantiations of the idealised autha protocol and oeke protocol. our result shows that the autha protocol can be instantiated in an insecure way, and that there are no well defined (let alone rigorous) ways to distinguish between secure and insecure instantiations. thus, without a rigorous metric for ideal-ciphers, the value of provable security in ideal cipher model is limited.
the closure properties on real numbers under limits and computable operators. in effective analysis, various classes of real numbers are discussed. for example, the classes of computable, semi-computable, weakly computable, recursively approximable real numbers, etc. all these classes correspond to some kind of (weak) computability of the real numbers. in this paper we discuss mathematical closure properties of these classes under the limit, effective limit and computable function. among others, we show that the class of weakly computable real numbers is not closed under effective limit and partial computable functions while the class of recursively approximable real numbers is closed under effective limit and partial computable functions.
divergence bounded computable real numbers. a real x is called h-bounded computable, for some function h: n → n, if there is a computable sequence (xs) of rational numbers which converges to x such that, for any n ∈ at most h(n) non-overlapping pairs of its members are separated by a distance larger than 2-n. in this paper we discuss properties of h-bounded computable reals for various functions h. we will show a simple sufficient condition for a class of functions h such that the corresponding h-bounded computable reals form an algebraic field. a hierarchy theorem for h-bounded computable reals is also shown. besides we compare semi-computability and weak computability with the h-bounded computability for special functions h.
connections among nonlinearity, avalanche and correlation immunity. nonlinear boolean functions play an important role in the design of block ciphers, stream ciphers and one-way hash functions. over the years researchers have identified a number of indicators that forecast nonlinear properties of these functions. studying the relationships among these indicators has been an area that has received extensive research. the focus of this paper is on the interplay of three notable nonlinear indicators, namely nonlinearity, avalanche and correlation immunity. we establish, for the first time, an explicit and simple lower bound on the nonlinearity nf of a boolean function f of n variables satisfying the avalanche criterion of degree p, namely, nf ≥ 2n-1 -2n-1-(1/2)p. we also identify all the functions whose nonlinearity attains the lower bound. as a further contribution of this paper, we prove that except for very few cases, the sum of the degree of avalanche and the order of correlation immunity of a boolean function of n variables is at most n-2. the new results obtained in this work further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, both go against correlation immunity.
the generalized xor lemma. the xor lemma states that a mapping is regular or balanced if and only if all the linear combinations of the component functions of the mapping are balanced boolean functions. the main contribution of this paper is to extend the xor lemma to more general cases where a mapping may not be necessarily regular. the extended xor lemma has applications in the design of substitution boxes or s-boxes used in secret key ciphers. it also has applications in the design of stream ciphers as well as one-way hash functions. of independent interest is a new concept introduced in this paper that relates the regularity of a mapping to subspaces.
a channel assignment problem for optical networks modelled by cayley graphs. a problem arising from a recent study of scalability of optical networks seeks to assign channels to the vertices of a network so that vertices distance 2 apart receive distinct channels. in this paper we introduce a general channel assignment scheme for cayley graphs on abelian groups, and derive upper bounds for the minimum number of channels needed for such graphs. as application we give a systematic way of producing near-optimal channel assignments for connected graphs admitting a vertex-transitive abelian group of automorphisms. hypercubes are examples of such graphs, and for them our near-optimal upper bound gives rise to the one obtained recently by wan.
a representation theorem for recovering contraction relations satisfying wci. a notion of an image structure associated with the canonical epistemic state is introduced. based on it, we get a representation result for recovering contraction inference relations satisfying the condition weak conjunctive inclusion (wci) in terms of f-standard epistemic agm states. in effect, this result establishes a representation theorem for belief contraction functions satisfying agm postulates (k-1) - (k-7), and rott's (wci) and (k-8c), and hence generalizes rott's corresponding result in the finite framework.
on the complexity of unsigned translocation distance. translocation is one of the basic operations for genome rearrangement. translocation distance is the minimum number of translocations required to transform one genome into the other. in this paper, we show that computing the translocation distance for unsigned genomes is np-hard. moreover, we show that approximating the translocation distance for unsigned genomes within ratio 1.00017 is np-hard.
normal conditions for inference relations and injective models. although fruitful representation results induced by some kinds of injective models, e.g., filtered, ranked and quasi-linear injective models, etc., have been established in the literature, it is still an open problem to characterize the family of all injective inference relations in terms of rules. the type of postulates appearing in recent literature seems to be unable to characterize this family. this brings up an interesting theoretical problem: what kind of injective inference relations may be characterized by existent types of postulates? this paper makes an initial step to answer this question. to this end, a notion of a normal condition is introduced, which subsumes all horn and non-horn conditions presented in the literature. we obtain some results on injective models generating inferences characterized by normal conditions, and show that these injective models must be specific standard models. moreover, for any set of injective models determined only by a structural property of preferential orders, if the family of inference relations induced by it can be characterized by normal conditions, then it must be a subset of filtered models in this circumstance. thus, its associated inference relations satisfy the non-horn rule disjunctive rationality.