EuDML | Browse

Let $K$ be a one-variable function field over a field of constants of characteristic 0. Let $R$ be a holomorphy subring of $K$ , not equal to $K$ . We prove the following undecidability results for $R$ : if $K$ is recursive, then Hilbert’s Tenth Problem is undecidable in $R$ . In general, there exist $x_{1}, ..., x_{n} \in R$ such that there is no algorithm to tell whether a polynomial equation with coefficients in $ℚ (x_{1}, ..., x_{n})$ has solutions in $R$ .

Disconnectedness of Sublevel Sets of Some Riemannian.

A. Nabutovsky (1996)

Geometric and functional analysis

Existential interpretation. II.

Yuri Gurevich (1982)

Archiv für mathematische Logik und Grundlagenforschung

Groups of automatic automorphisms of some automatic structures.

Vinokurov, N.S. (2006)

Sibirskie Ehlektronnye Matematicheskie Izvestiya [electronic only]

Highly Undecidable Problems For Infinite Computations

Olivier Finkel (2009)

RAIRO - Theoretical Informatics and Applications

We show that many classical decision problems about 1-counter ω-languages, context free ω-languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”. In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all Π½ -complete for context-free ω-languages or for infinitary rational...

Metamathematical discussion of some affine geometries

L. Szczerba, Alfred Tarski (1979)

Fundamenta Mathematicae

Model-theoretic properties of cause-and-effect structures

Kurt Hauschild (1982)

Commentationes Mathematicae Universitatis Carolinae

On a connection between the word problem and decidability of the equational theory.

Popov, V.Yu. (2000)

Siberian Mathematical Journal

Partial conservativity revisited

Petr Hájek (1987)

Commentationes Mathematicae Universitatis Carolinae

Recursive inseparability of the sets of identically valid and finitely refutable formulas of some elementary theories of varieties.

Ursu, V.I. (2000)

Siberian Mathematical Journal

Some diophantine forms of Gödel's theorem.

V.H. Dyson, J.P. Jones (1982)

Archiv für mathematische Logik und Grundlagenforschung

Some undecidable theories with monadic predicates and without equality.

Hans Kleine Büning (1981)

Archiv für mathematische Logik und Grundlagenforschung

The computability potential scale of all finite algebras.

Pinus, A.G. (2007)

Sibirskij Matematicheskij Zhurnal

The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract)

Dana May Latch (1991)

Cahiers de Topologie et Géométrie Différentielle Catégoriques

Theories of orders on the set of words

Dietrich Kuske (2006)

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

It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of the subword...

Currently displaying 1 – 20 of 61

Page 1 Next