@article{doi:10.1137/0211001,
    Abstract = {Let \$\mathbb{C}\$ be the set of all straight-line programs with one input variable, x, using the following instruction set: \$y \leftarrow 0\$, \$y \leftarrow 1\$, \$y \leftarrow y + w\$, \$y \leftarrow y - w\$, \$y \leftarrow y * w\$, and \$y \leftarrow \lfloor y/w \rfloor \$. We show that two programs in \$\mathbb{C}\$ are equivalent over integer inputs if and only if they are equivalent on all inputs x such that \$|x| \leqq 2^{2^{\lambda r^2 } } \$ (\$\lambda \$ is a fixed positive constant and r is the maximum of the lengths of the programs). In contrast, we prove that the zero-equivalence problem (deciding whether a program outputs 0 for all inputs) is undecidable for programs with two input variables. An interesting corollary is the following: Let \$\mathbb{N}\$ be the set of natural numbers and f be any total one-to-one function from \$\mathbb{N}\$ onto \$\mathbb{N} \times \mathbb{N}\$ (f is called a pair generator. Such functions are useful in recursive function theory and computability theory.) Then f cannot be computed by any program in \$\mathbb{C}\$.},
    Author = {Ibarra, Oscar H. and Leininger, Brian S.},
    EPrint = {https://doi.org/10.1137/0211001},
    File = {Straight-Line Programs with One Input Variable - ibarra1982.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {1},
    Pages = {1--14},
    Title = {Straight-Line Programs with One Input Variable},
    URL = {https://doi.org/10.1137/0211001},
    Volume = {11},
    Year = {1982},
    bdsk-url-1 = {https://doi.org/10.1137/0211001},
    date-added = {2023-08-26 10:41:57 +0200},
    date-modified = {2023-08-26 10:42:03 +0200},
    doi = {10.1137/0211001}
}

@article{doi:10.1137/0211001, Abstract = {Let \$\mathbb{C}\$ be the set of all straight-line programs with one input variable, x, using the following instruction set: \$y \leftarrow 0\$, \$y \leftarrow 1\$, \$y \leftarrow y + w\$, \$y \leftarrow y - w\$, \$y \leftarrow y * w\$, and \$y \leftarrow \lfloor y/w \rfloor \$. We show that two programs in \$\mathbb{C}\$ are equivalent over integer inputs if and only if they are equivalent on all inputs x such that \$|x| \leqq 2^{2^{\lambda r^2 } } \$ (\$\lambda \$ is a fixed positive constant and r is the maximum of the lengths of the programs). In contrast, we prove that the zero-equivalence problem (deciding whether a program outputs 0 for all inputs) is undecidable for programs with two input variables. An interesting corollary is the following: Let \$\mathbb{N}\$ be the set of natural numbers and f be any total one-to-one function from \$\mathbb{N}\$ onto \$\mathbb{N} \times \mathbb{N}\$ (f is called a pair generator. Such functions are useful in recursive function theory and computability theory.) Then f cannot be computed by any program in \$\mathbb{C}\$.}, Author = {Ibarra, Oscar H. and Leininger, Brian S.}, EPrint = {https://doi.org/10.1137/0211001}, File = {Straight-Line Programs with One Input Variable - ibarra1982.pdf}, Journal = {SIAM Journal on Computing}, Number = {1}, Pages = {1--14}, Title = {Straight-Line Programs with One Input Variable}, URL = {https://doi.org/10.1137/0211001}, Volume = {11}, Year = {1982}, bdsk-url-1 = {https://doi.org/10.1137/0211001}, date-added = {2023-08-26 10:41:57 +0200}, date-modified = {2023-08-26 10:42:03 +0200}, doi = {10.1137/0211001} }