Search

In the first part we show that the exponential diophantine problem for Q is algorithmically undecidable. The second part studies the question about a continuous approximation function for the square root in the rationals, in the larger context of continuous choice functions for generic predicates. [ABSTRACT FROM AUTHOR]

A model-theoretic proof of the fact that all infinite Abelian groups P not equal to NP in the sense of binary nondeterminism is given.

Abstract: A recurrent -dimensional sequence is given by fixing particular sequences , as initial conditions and a rule of recurrence for . We generalize this concept to an arbitrary number of dimensions and of predecessors. We give a criterion for a general -dimensional recurrent sequence to be alternatively produced by an -dimensional substitution — i.e. to be an automatic sequence. We show also that if the initial conditions are -automatic and the rule of recurrence is an -affine function, then the -dimensional sequence is -automatic. Consequently all such -dimensional sequences can be also defined by -dimensional substitution. Finally we show various positive examples, but also a -dimensional recurrent sequence which is not -automatic for any . As a byproduct we show that for polynomials with and , the characteristic sequence of the set is not -automatic for any . [Copyright &y& Elsevier]

We prove that if a recurrent two-dimensional sequence with periodic initial conditions coincides in a sufficiently large starting square with a two-dimensional sequence produced by an expansive system of context-free substitutions, then they must coincide everywhere. We apply this result for some examples built up by homomorphisms of finite abelian p-groups, in particular for Pascal's Triangle modulo pk, Pascal's Triangles modulo 2 with non-trivial periodic borders, and Sierpinski's Carpets with non-trivial periodic border. All these particular cases justify the conjecture that recurrent two-dimensional sequences generated by homomorphisms of finite abelian p-groups with periodic initial conditions can always be alternatively generated by expansive systems of context-free substitutions. [ABSTRACT FROM AUTHOR]

Abstract: If a recurrent two-dimensional sequence with initial conditions defined by linear substitution and a two-dimensional sequence that is generated by planar substitution are identical over a sufficiently large initial square, then they will coincide over all. After proving this general principle, we apply it to some concrete examples. One of them, the Thue–Morse–Pascal two-dimensional sequence, is defined by two copies of the Prouhet–Thue–Morse sequence as pair of initial conditions and by the Pascal Triangle Addition modulo 2 as rule of recurrence. As it follows, the Thue–Morse–Pascal two-dimensional sequence is the result of 15 substitution rules, each of them consisting of the substitution of some matrix with an matrix. [Copyright &y& Elsevier]

The author used the automatic proof procedure introduced in [1] and verified that the 4096 homomorphic recurrent double sequences with constant borders defined over Klein's Vierergruppe K and the 4096 linear recurrent double sequences with constant border defined over the matrix ring M2(...2) can be also produced by systems of substitutions with finitely many rules. This permits the definition of a sound notion of geometric content for most of these sequences, more exactly for those which are not primitive. We group the 4096 many linear recurrent double sequences with constant border I over the ring M2(...2) in 90 geometric types. The classification over Klein's Vierergruppe Kis not explicitly displayed and consists of the same geometric types like for M2(...2), but contains more exceptions. There are a lot of cases of unsymmetric double sequences converging to symmetric geometric contents. We display also geometric types occurring both in a monochromatic and in a dichromatic version. [ABSTRACT FROM AUTHOR]

We prove that if a recurrent double sequence coincide in a sufficiently large starting square with a double sequence produced by context-free substitutions, then they must coincide everywhere. We apply this result for some examples. [ABSTRACT FROM AUTHOR]

We show that the set of natural numbers has an exponential diophantine definition in the rationals. It follows that the corresponding decision problem is undecidable. [ABSTRACT FROM AUTHOR]

Classical results of additive number theory lead to the undecidability of the existence of solutions for diophantine equations in given special sets of integers. Those sets which are images of polynomials are covered by a more general result in the second section. In contrast, restricting diophantine equations to images of exponential functions with natural bases leads to decidable problems, as proved in the third section. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Abstract: The paper presents two situations where unit-cost complexity results are closely related with results from the classical computability. In Section 2 we study an important theorem by Koiran and Fournier from an axiomatic point of view. It is proved that the algebraic Knapsack problem belongs to P over some ordered abelian semi-group iff classically. In this case there would exist a unit-cost machine solving the algebraic Knapsack problem over all ordered abelian semi-groups in some uniform polynomial time. In Section 3 we apply the theorem of Matiyasevich in order to construct a ring with and such that its polynomial hierarchy does not collapse at any level. [Copyright &y& Elsevier]

We prove that all infinite Boolean rings (algebras) have the property P ≠ NP according to the digital (binary) nondeterminism. [ABSTRACT FROM AUTHOR]

Genera connections between quantifier elimination and decidability for first order theories are studied and exemplified. [ABSTRACT FROM AUTHOR]