@article{IBARRA198347,
    Abstract = {The complexity of the zero-inequivalence problem (deciding if a program outputs a nonzero value for some nonnegative integer input) for several simple classes of loop programs is studied. In particular, we show that the problem is NP-complete for L1-programs with only one input variable and two auxiliary variables. These are programs over the instruction set x ← 0, x ← x + 1, x ← y, do x {\ldots} end, where do-loops cannot be nested. For K1-programs, where the instruction set is x ← x + 1, x ← x ∸ 1, do x {\ldots} end, zero-inequivalence is NP-complete even for programs with only one input variable and one auxiliary variable. These results may be the best possible since there is a class of programs which properly contains two-variable L1-programs and one-variable K1-programs with a polynomial time decidable equivalence problem. Addition of other constructs, e.g., allowing K1-programs to use instruction x ← x + y, makes the zero-inequivalence problem undecidable.},
    Author = {Ibarra, Oscar H. and Leininger, Brian S.},
    File = {On the Zero-inequivalence Problem far Loop Programs - 1-s2.0-002200008390020X-main.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Number = {1},
    Pages = {47--64},
    Title = {On the Zero-inequivalence Problem for Loop Programs},
    URL = {https://www.sciencedirect.com/science/article/pii/002200008390020X},
    Volume = {26},
    Year = {1983},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/002200008390020X},
    bdsk-url-2 = {https://doi.org/10.1016/0022-0000(83)90020-X},
    date-added = {2023-08-26 10:38:42 +0200},
    date-modified = {2023-08-26 10:40:18 +0200},
    doi = {10.1016/0022-0000(83)90020-X}
}

@article{IBARRA198347, Abstract = {The complexity of the zero-inequivalence problem (deciding if a program outputs a nonzero value for some nonnegative integer input) for several simple classes of loop programs is studied. In particular, we show that the problem is NP-complete for L1-programs with only one input variable and two auxiliary variables. These are programs over the instruction set x ← 0, x ← x + 1, x ← y, do x {\ldots} end, where do-loops cannot be nested. For K1-programs, where the instruction set is x ← x + 1, x ← x ∸ 1, do x {\ldots} end, zero-inequivalence is NP-complete even for programs with only one input variable and one auxiliary variable. These results may be the best possible since there is a class of programs which properly contains two-variable L1-programs and one-variable K1-programs with a polynomial time decidable equivalence problem. Addition of other constructs, e.g., allowing K1-programs to use instruction x ← x + y, makes the zero-inequivalence problem undecidable.}, Author = {Ibarra, Oscar H. and Leininger, Brian S.}, File = {On the Zero-inequivalence Problem far Loop Programs - 1-s2.0-002200008390020X-main.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Number = {1}, Pages = {47--64}, Title = {On the Zero-inequivalence Problem for Loop Programs}, URL = {https://www.sciencedirect.com/science/article/pii/002200008390020X}, Volume = {26}, Year = {1983}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/002200008390020X}, bdsk-url-2 = {https://doi.org/10.1016/0022-0000(83)90020-X}, date-added = {2023-08-26 10:38:42 +0200}, date-modified = {2023-08-26 10:40:18 +0200}, doi = {10.1016/0022-0000(83)90020-X} }