All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 31

Showing per page

Wadge degrees of ω -languages of deterministic Turing machines

Victor Selivanov (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 ξ = ω 1 CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].

Wadge Degrees of ω-Languages of Deterministic Turing Machines

Victor Selivanov (2010)

RAIRO - Theoretical Informatics and Applications

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].

Watson-Crick pushdown automata

Kingshuk Chatterjee, Kumar S. Ray (2017)

Kybernetika

A multi-head 1-way pushdown automaton with k heads is a pushdown automaton with k 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...

Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces

Nils Reich (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

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...

Weak mixing and eigenvalues for Arnoux-Rauzy sequences

Julien Cassaigne, Sébastien Ferenczi, Ali Messaoudi (2008)

Annales de l’institut Fourier

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.

Weak solutions of a parabolic-elliptic type system for image inpainting

Zhengmeng Jin, Xiaoping Yang (2010)

ESAIM: Control, Optimisation and Calculus of Variations

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.

Web Interface and Collection for Mathematical Retrieval : WebMIaS and MREC

Líška, Martin, Sojka, Petr, Růžička, Michal, Mravec, Petr (2011)

Towards a Digital Mathematics Library. Bertinoro, Italy, July 20-21st, 2011

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...

Weighting quantitative and qualitative variables in clustering methods.

Karina Gibert, Ulises Cortés (1997)

Mathware and Soft Computing

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...

Weightreducing grammars and ultralinear languages

Ulrike Brandt, Ghislain Delepine, Hermann K.-G. Walter (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

Weightreducing grammars and ultralinear languages

Ulrike Brandt, Ghislain Delepine, Hermann K.-G. Walter (2010)

RAIRO - Theoretical Informatics and Applications

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.

Well quasi-orders, unavoidable sets, and derivation systems

Flavio D'Alessandro, Stefano Varricchio (2006)

RAIRO - Theoretical Informatics and Applications

Let I be a finite set of words and ⇒ I * be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let L I ϵ be the set of words u such that ϵ ⇒ I * u . We prove that the set I is unavoidable if and only if the relation ⇒ I * is a well quasi-order on the set L I ϵ . This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.

What is the inverse of repeated square and multiply algorithm?

H. Gopalkrishna Gadiyar, K. M. Sangeeta Maini, R. Padma, Mario Romsy (2009)

Colloquium Mathematicae

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...

What machines can and cannot do.

Luis M. Laita, Roanes-Lozano, Luis De Ledesma Otamendi (2007)

RACSAM

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”...

Currently displaying 1 – 20 of 31

Page 1 Next