Journal article
On the solvability of a class of diophantine equations and applications
Theoretical computer science, Vol.352(1), pp.342-346
2006
Handle:
https://hdl.handle.net/2376/117214
Abstract
For
1
⩽
i
⩽
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
,
…
,
x
n
with integer coefficients. Let
P
(
z
1
,
…
,
z
k
)
be a Presburger relation over the nonnegative integers. We show that the following problem is decidable:
Given:
R
1
,
…
,
R
k
and a Presburger relation
P.
Question: Are there nonnegative integer values for
y
,
x
1
,
…
,
x
n
such that for these values,
(
R
1
,
…
,
R
k
)
satisfies
P?
We also give some applications to decision problems concerning counter machines.
Metrics
10 Record Views
Details
- Title
- On the solvability of a class of diophantine equations and applications
- Creators
- Oscar H Ibarra - Department of Computer Science, University of California, Santa Barbara, CA 93106, USAZhe Dang - School of Electrical Engineering & Computer Science, Washington State University, Pullman, WA 99164, USA
- Publication Details
- Theoretical computer science, Vol.352(1), pp.342-346
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Publisher
- Elsevier B.V
- Identifiers
- 99900548007901842
- Language
- English
- Resource Type
- Journal article