scientific article; zbMATH DE number 3336816
From MaRDI portal
Publication:5613949
zbMath0212.33401MaRDI QIDQ5613949
Publication date: 1970
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Undecidability and degrees of sets of sentences (03D35) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25)
Related Items
The Diophantine problem in the classical matrix groups ⋮ Craig Interpolation in the Presence of Non-linear Constraints ⋮ The expressibility of languages and relations by word equations ⋮ Solvable problems for transformers with reversal-bounded counters ⋮ Size-based termination of higher-order rewriting ⋮ On genuinely time bounded computations ⋮ The quest for Diophantine finite-fold-ness ⋮ Diophantine equations with three monomials ⋮ Analysis and Transformation of Constrained Horn Clauses for Program Verification ⋮ On two-way weak counter machines ⋮ New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023 ⋮ Proving correctness of imperative programs by linearizing constrained Horn clauses ⋮ Differential calculuses on group algebras ⋮ Unnamed Item ⋮ Undecidability of polynomial inequalities in weighted graph homomorphism densities ⋮ Характеризация чисел Фибоначчи ⋮ Reasoning in the Bernays-Schönfinkel-Ramsey Fragment of Separation Logic ⋮ Unnamed Item ⋮ On the Complexity of the Planar Slope Number Problem ⋮ Proving Quadratic Derivational Complexities Using Context Dependent Interpretations ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Representation of squares by monic second degree polynomials in the field of 𝑝-adic meromorphic functions ⋮ A partial solution for D-unification based on a reduction to AC 1-unification ⋮ Unnamed Item ⋮ SOLVING DIFFERENCE EQUATIONS IN SEQUENCES: UNIVERSALITY AND UNDECIDABILITY ⋮ Martin Davis and Hilbert’s Tenth Problem ⋮ What Is Essential Unification? ⋮ ON GENERIC COMPLEXITY OF DECIDABILITY PROBLEM FOR DIOPHANTINE SYSTEMS IN THE SKOLEM’S FORM ⋮ ON GENERIC UNDECIDABILITY OF HILBERT’S TENTH PROBLEM FOR POLYNOMIAL TREES ⋮ DECIDABILITY OF THE RESTRICTED THEORIES OF A CLASS OF PARTIAL ORDERS ⋮ Zur Theorie Der Spektralen Darstellung Von Prädikaten Durch Ausdrücke Der Prädikatenlogik 1. Stufe ⋮ A theory for Log-Space and NLIN versus co-NLIN ⋮ Unnamed Item ⋮ A survey of computational complexity results in systems and control ⋮ Kolmogorov Complexity Theory over the Reals ⋮ Equations in free metabelian groups ⋮ Diophantine sets of polynomials over number fields ⋮ A proof of negative answer to Hilbert's $10$th problem ⋮ Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computational complexity of quantifier-free negationless theory of field of rational numbers ⋮ Decision Procedures for Multisets with Cardinality Constraints ⋮ Satisfiability of Algebraic Circuits over Sets of Natural Numbers ⋮ Hilbert's Tenth Problem in Coq ⋮ ОБ УРАВНЕНИЯХ И НЕРАВЕНСТВАХ В СЛОВАХ И ДЛИНАХ ⋮ Emptiness Problems for Integer Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ On the passage from local to global in number theory ⋮ Some New Probability Operators ⋮ On some reducibility and existential interpretability of structures ⋮ Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint ⋮ Efficient symbolic analysis of programs ⋮ Further results on Hilbert's tenth problem ⋮ Diophantine questions in the class of finitely generated nilpotent groups ⋮ Exact divisibility by powers of the integers in the Lucas sequence of the first kind ⋮ The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem ⋮ Exact divisibility by powers of the integers in the Lucas sequences of the first and second kinds ⋮ Mechanically proving termination using polynomial interpretations ⋮ An infinite version of Arrow's theorem in the effective setting ⋮ Diophantine representations of linear recurrences. I ⋮ Fibonacci linear forms and parallel arithmetic algorithms for large numbers ⋮ Recursively enumerable sets of polynomials over a finite field ⋮ Nominal syntax with atom substitutions ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Emptiness problems for integer circuits ⋮ On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram \(\mathbb A_n\) ⋮ Towards finite-fold Diophantine representations ⋮ A survey on Büchi's problem: new presentations and open problems ⋮ Universal theory of nilpotent groups ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ An analogue of Hilbert's 10th problem for fields of meromorphic functions over non-Archimedean valued fields ⋮ ABS methods for continuous and integer linear equations and optimization ⋮ Automated analysis of cryptographic assumptions in generic group models ⋮ An algorithmic problem for nilpotent groups and rings ⋮ Semiautomatic structures ⋮ Decidability of the universal theory of natural numbers with addition and divisibility ⋮ A new proof of the theorem on exponential diophantine representation of enumerable sets ⋮ Succinct Diophantine-satisfiability arguments ⋮ A modal logic framework for reasoning about comparative distances and topology ⋮ What does a group algebra of a free group ``know about the group? ⋮ On an undecidable problem related to difference equations with parameters ⋮ On nonstochastic languages and homomorphic images of stochastic languages ⋮ 2DST mappings of languages and related problems ⋮ A mesh algorithm for principal quadratic forms ⋮ Solving word equations modulo partial commutations ⋮ Endomorphisms of elliptic curves and undecidability in function fields of positive characteristic. ⋮ An arithmetical characterization of NP ⋮ Uniform existential interpretation of arithmetic in rings of functions of positive characteristic ⋮ Representing integers by multilinear polynomials ⋮ Inferring answers to queries ⋮ Hilbert's tenth problem for rings of rational functions ⋮ Diophantine representations of linear recurrent sequences. II ⋮ Recursively enumerable sets of polynomials over a finite field are Diophantine ⋮ Weak quantifier elimination for the full linear theory of the integers ⋮ Positive existential definability of multiplication from addition and the range of a polynomial ⋮ Definability of Frobenius orbits and a result on rational distance sets ⋮ Recognition and complexity of point visibility graphs ⋮ Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games ⋮ Norm bounds and underestimators for unconstrained polynomial integer minimization ⋮ Friedberg splittings of recursively enumerable sets ⋮ Hilbert's tenth problem for weak theories of arithmetic ⋮ Computability of recurrence equations ⋮ Knapsack problem for nilpotent groups ⋮ Hilbert's tenth problem is of unification type zero ⋮ On a Diophantine representation of the predicate of provability ⋮ The scope of Gödel's first incompleteness theorem ⋮ A new method for undecidability proofs of first order theories ⋮ Hensley's problem for complex and non-Archimedean meromorphic functions ⋮ Diophantine equations and the generalized Riemann hypothesis ⋮ Unsolvability of some optimization problems ⋮ The analogue of Büchi's problem for function fields ⋮ Some new results on decidability for elementary algebra and geometry ⋮ New techniques and results in multidimensional problems ⋮ Computational power of infinite quantum parallelism ⋮ Satisfiability of algebraic circuits over sets of natural numbers ⋮ Diophantine complexity ⋮ The equality problem for vector addition systems is undecidable ⋮ NP-complete decision problems for binary quadratics ⋮ Properties of the solutions of equations in a free semigroup ⋮ On maximal chains of systems of word equations ⋮ Some decision problems for polynomial mappings ⋮ Extended universal theories of the integers ⋮ On finding test data sets for loop free programs ⋮ Existential arithmetization of Diophantine equations ⋮ Powerful values of polynomials and a conjecture of Vojta ⋮ Exact divisibility by powers of the Pell and associated Pell numbers ⋮ Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings ⋮ Infiniteness sets of primes, admitting diophantine representations in eight variables ⋮ A new technique for obtaining diophantine representations via elimination of bounded universal quantifiers ⋮ Problems equivalent to rational Diophantine solvability ⋮ A matrix approach for divisibility properties of the generalized Fibonacci sequence ⋮ On the computational power of context-free PC grammar systems ⋮ Semi-algebraic sets of \(f\)-vectors ⋮ Quantifier-free and one-quantifier systems ⋮ Diophantine representations of the sequence of solutions of the Pell equation ⋮ On some bounded semiAFLs and AFLs ⋮ Constructive mathematics and mathematical logic. Part X. Transl. from the Russian ⋮ On the theories of free solvable groups ⋮ Balance problems for integer circuits ⋮ A view of computability on term algebras ⋮ A class of filled functions for box constrained continuous global optimization ⋮ Propositional dynamic logic of nonregular programs ⋮ Generation problems ⋮ Polynomial time computations in models of ET ⋮ Counter machines and verification problems. ⋮ On trees without hyperimmune branches ⋮ An undecidability result for the asymptotic theory of \(p\)-adic fields ⋮ Array theory of bounded elements and its applications ⋮ A note on Presburger arithmetic with array segments, permutation and equality
