Search results for " processing"
showing 10 items of 7549 documents
$(BV,L^p)$-decomposition, $p=1,2$, of Functions in Metric Random Walk Spaces
2019
In this paper we study the $(BV,L^p)$-decomposition, $p=1,2$, of functions in metric random walk spaces, a general workspace that includes weighted graphs and nonlocal models used in image processing. We obtain the Euler-Lagrange equations of the corresponding variational problems and their gradient flows. In the case $p=1$ we also study the associated geometric problem and the thresholding parameters.
Measure-free conditioning and extensions of additive measures on finite MV-algebras
2010
Using the well known representation of any finite MV-algebra as a product of finite MV-chains as factors, we obtain a representation of its canonical extension as a Girard algebra product of the canonical extensions of the MV-chain factors. Based on this representation and using the results from our last paper, we characterize the additive measures on any finite MV-algebra resp. the weakly and the strongly additive measures on its canonical Girard algebra extension, and that as convex combinations of the corresponding measures on the respective factors. After that we apply the results to measure-free defined conditional events which for this reason are considered as elements of the canonica…
Analysis of Optimal High Resolution and Fixed Rate Scalar Quantization
2009
In 2001, Hui and Neuhoff proposed a uniform quantizer with overload for the quantization of scalar signals and derived the asymptotically optimal size of the quantization bins in the high-bitrate limit. The purpose of the present paper is to prove a quantitatively more precise version of this result which, at the same time, is valid for a more general, quite natural class of probability distributions that requires only little regularity and includes, for instance, positive Lipschitz-continuous functions of unit integral.
Capabilities of Ultrametric Automata with One, Two, and Three States
2016
Ultrametric automata use p-adic numbers to describe the random branching of the process of computation. Previous research has shown that ultrametric automata can have a significant decrease in computing complexity. In this paper we consider the languages that can be recognized by one-way ultrametric automata with one, two, and three states. We also show an example of a promise problem that can be solved by ultrametric integral automaton with three states.
Root-restricted Kleenean rotations
2010
We generalize the Kleene theorem to the case where nonassociative products are used. For this purpose, we apply rotations restricted to the root of binary trees.
Unavoidable sets and circular splicing languages
2017
Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. In this paper, we focus on the still unknown relations between regular languages and circular splicing systems with a finite initial set and a finite set R of rules represented by a pair of letters ( ( 1 , 3 ) -CSSH systems). When R = A × A , it is known that the set of all words corresponding to the splicing language belongs to the class of pure unitary languages, introduced by Ehrenfeucht, Haussler, Rozenberg in 1983. They also provided a characteriza…
Querying the Guarded Fragment with Transitivity
2016
We study the problem of answering a union of Boolean conjunctive queries q against a database Δ, and a logical theory φ which falls in the guarded fragment with transitive guards (GF + TG). We trace the frontier between decidability and undecidability of the problem under consideration. Surprisingly, we show that query answering under GF2 + TG, i.e., the two-variable fragment of GF + TG, is already undecidable (even without equality), whereas its monadic fragment is decidable; in fact, it is 2exptime-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable. © 2013 Springer-Verlag.
Verbal sets and cyclic coverings
2010
Abstract We consider groups G such that the set of all values of a fixed word w in G is covered by a finite set of cyclic subgroups. Fernandez-Alcober and Shumyatsky studied such groups in the case when w is the word [ x 1 , x 2 ] , and proved that in this case the corresponding verbal subgroup G ′ is either cyclic or finite. Answering a question asked by them, we show that this is far from being the general rule. However, we prove a weaker form of their result in the case when w is either a lower commutator word or a non-commutator word, showing that in the given hypothesis the verbal subgroup w ( G ) must be finite-by-cyclic. Even this weaker conclusion is not universally valid: it fails …
Combinatorics of Finite Words and Suffix Automata
2009
The suffix automaton of a finite word is the minimal deterministic automaton accepting the language of its suffixes. The states of the suffix automaton are the classes of an equivalence relation defined on the set of factors. We explore the relationship between the combinatorial properties of a finite word and the structural properties of its suffix automaton. We give formulas for expressing the total number of states and the total number of edges of the suffix automaton in terms of special factors of the word.
Sensitivity Versus Certificate Complexity of Boolean Functions
2016
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomially related to block sensitivity. However, it has been notoriously hard to obtain even exponential bounds. Since block sensitivity is known to be polynomially related to certificate complexity, an equivalent of proving this conjecture would be showing that the certificate complexity is polynomially related to sensitivity. Previously, it has been shown that $$bsf \le Cf \le 2^{sf-1} sf - sf-1$$. In this work, we give a better upper bound of $$bsf \le Cf \le \max \left 2^{sf-1}\left sf-\frac{1}{3}\right , sf\right $…