On the solvability of a class of Diophantine equations and applications
type: Item
instance of: scholarly article
title: On the solvability of a class of Diophantine equations and applications
zbMATH Open document ID: 1120.11017
author: Oscar H. Ibarra
author: Zhe Dang
published in: Theoretical Computer Science
publication date: 2006-03-24T00:00:00Z
review text: For \(1\leq i\leq k\), let \(R_i\) denote \(p_i(y)F_i+G_i\), where \(p_i(y)\) is a polynomial in \(y\) with integer coefficients, and \(F_i, G_i\), are linear polynomials in \(x_1, \dots,x_n\) with integer coefficients. Let \(P(z_1,\dots,z_k)\) be a Presburger relation over the nonnegative integers. It is shown that the following problem is decidable: Given: \(R_1,\dots,R_k\) and a Presburger relation \(P\). Question: Are there nonnegative integer values for \(y, x_1,\dots,x_n\) such that for these values, \((R_1,\ldots,R_k)\) satisfies \(P\)? Some applications to decision problems concerning counter machines are also presented.
reviewed by: Edward L. Cohen
Mathematics Subject Classification ID: 11D41
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5015114
zbMATH Keywords: Diophantine equations
zbMATH Keywords: counter machine
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.12.001
OpenAlex ID: W2053402117
cites work: Flat Parametric Counter Automata
cites work: Some decision problems concerning semilinearity and commutation.
cites work: On two-way FA with monotonic counters and quadratic Diophantine equations
cites work: Q4412126
cites work: New Decidability Results Concerning Two-Way Counter Machines
cites work: The Diophantine Problem for Addition and Divisibility
cites work: Q3992465
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
DOI: 10.1016/J.TCS.2005.12.001
description: scientific article; zbMATH DE number 5015114