Search results for "Computation theory"
showing 10 items of 336 documents
Frames for fusions of modal logics
2018
Let us consider multimodal logics and . We assume that is characterised by a class of connected frames, and there exists an -frame with a so-called -starting point. Similarly, the logic is characterised by a class of connected frames, and there exists an -frame with a -starting point. Using isomorphic copies of the frames and , we construct a connected frame which characterises the fusion . The frame thus obtained has some useful properties. Among others, is countable if both and are countable, and there is a special world of the frame such that any formula is valid in the frame if and only if it is valid at the point . We also describe a similar construction where we assume the existence o…
The ideal duplication
2021
AbstractIn this paper we present and study the ideal duplication, a new construction within the class of the relative ideals of a numerical semigroup S, that, under specific assumptions, produces a relative ideal of the numerical duplication $$S\bowtie ^b E$$ S ⋈ b E . We prove that every relative ideal of the numerical duplication can be uniquely written as the ideal duplication of two relative ideals of S; this allows us to better understand how the basic operations of the class of the relative ideals of $$S\bowtie ^b E$$ S ⋈ b E work. In particular, we characterize the ideals E such that $$S\bowtie ^b E$$ S ⋈ b E is nearly Gorenstein.
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
2012
We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…
Forests and pattern-avoiding permutations modulo pure descents
2018
Abstract We investigate an equivalence relation on permutations based on the pure descent statistic. Generating functions are given for the number of equivalence classes for the set of all permutations, and the sets of permutations avoiding exactly one pattern of length three. As a byproduct, we exhibit a permutation set in one-to-one correspondence with forests of ordered binary trees, which provides a new combinatorial class enumerated by the single-source directed animals on the square lattice. Furthermore, bivariate generating functions for these sets are given according to various statistics.
Extending the star order to Rickart rings
2015
Star partial order was initially introduced for semigroups and rings with (proper) involution. In particular, this order has recently been studied on Rickart *-rings. It is known that the star order in such rings can be characterized by conditions not involving involution explicitly. Owing to these characterizations, the order can be extended to certain special Rickart rings named strong in the paper; this extension is the objective of the paper. The corresponding order structure of strong Rickart rings is studied more thoroughly. In particular, the most significant lattice properties of star-ordered Rickart *-rings are successfully transferred to strong Rickart rings; also several new resu…
Tighter Relations between Sensitivity and Other Complexity Measures
2014
The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
2013
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] uses \(O(\sqrt{N \log{N}})\) steps and finds a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqrt{N}\). This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additional \(O(\sqrt{\log{N}})\) factor to the number of steps, making it \(O(\sqrt{N} \log{N})\).
Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
2017
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly k or l of the n input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
On the inductive inference of recursive real-valued functions
1999
AbstractWe combine traditional studies of inductive inference and classical continuous mathematics to produce a study of learning real-valued functions. We consider two possible ways to model the learning by example of functions with domain and range the real numbers. The first approach considers functions as represented by computable analytic functions. The second considers arbitrary computable functions of recursive real numbers. In each case we find natural examples of learnable classes of functions and unlearnable classes of functions.
Linear-size suffix tries
2016
Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and lin…