We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
We describe Wadge degrees of ω-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξω where ξ = ω1CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
A multi-head 1-way pushdown automaton with heads is a pushdown automaton with 1-way read heads on the input tape and a stack. It was previously shown that the deterministic variant of the model cannot accept all the context free languages. In this paper, we introduce a 2-tape, 2-head model namely Watson-Crick pushdown automata where the content of the second tape is determined using a complementarity relation, similar to Watson-Crick automata. We show computational powers of nondeterministic...
For a class of anisotropic integrodifferential operators arising as semigroup generators of Markov processes, we present a sparse tensor product wavelet compression scheme for the Galerkin finite element discretization of the corresponding integrodifferential equations u = f on [0,1]n with possibly large n. Under certain conditions on , the scheme is of essentially optimal and dimension independent complexity (h-1| log h |2(n-1)) without corrupting the convergence or smoothness requirements...
We define by simple conditions two wide subclasses of the so-called Arnoux-Rauzy systems; the elements of the first one share the property of (measure-theoretic) weak mixing, thus we generalize and improve a counter-example to the conjecture that these systems are codings of rotations; those of the second one have eigenvalues, which was known hitherto only for a very small set of examples.
In this paper we consider the initial boundary value problem of a parabolic-elliptic system for image inpainting, and establish the existence and uniqueness of weak solutions to the system in dimension two.
We demonstrate searching of mathematical expressions in technical digital libraries on a MREC collection of 439,423 real scientific documents with more than 158 million mathematical formulae. Our solution—the WebMIaS system—allows the retrieval of mathematical expressions written in TeX or MathML. TeX queries are converted on-the-fly into tree representations of Presentation MathML, which is used for indexing. WebMIaS allows complex queries composed of plain text and mathematical formulae, using...
Description of individuals in ill-structured domains produces messy data matrices. In this context, automated classification requires the management of those kind of matrices. One of the features involved in clustering is the evaluation of distances between individuals. Then, a special function to calculate distances between individuals partially simultaneously described by qualitative and quantitative variables is required.In this paper properties and details of the metrics used by Klass in this...
We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.
We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.
Let I be a finite set of words and be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let be the set of words u such that . We prove that the set I is unavoidable if and only if the relation is a well quasi-order on the set . This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.
It is well known that the repeated square and multiply algorithm is an efficient way of modular exponentiation. The obvious question to ask is if this algorithm has an inverse which would calculate the discrete logarithm and what is its time compexity. The technical hitch is in fixing the right sign of the square root and this is the heart of the discrete logarithm problem over finite fields of characteristic not equal to 2. In this paper a couple of probabilistic algorithms to compute the discrete...
In this paper, the questions of what machines cannot do and what they can do will be treated by examining the ideas and results of eminent mathematicians. Regarding the question of what machines cannot do, we will rely on the results obtained by the mathematicians Alan Turing and Kurt G¨odel. Turing machines, their purpose of defining an exact definition of computation and the relevance of Church-Turing thesis in the theory of computability will be treated in detail. The undecidability of the “Entscheidungsproblem”...