article

Free access

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

Authors:

Oscar H. Ibarra,

Shlomo MoranAuthors Info & Claims

Journal of the ACM (JACM), Volume 30, Issue 1

Pages 217 - 228

https://doi.org/10.1145/322358.322373

Published: 01 January 1983 Publication History

PDF eReader

References

[1]

ADLI/MAN, LTwo theorems on random polynomml time Proc. 19th Ann. IEEE Symp. on Foundatlons of Computer Soence, Ann Arbor, Mmh., 1978, pp 75-83.

Google Scholar

[2]

ADLEMAN, L., AND MANDI/RS, K. Reducablhty, randomness, and mtractabtlity. Proc. 9th Ann. ACM Syrup. on Theory of Computing, Boulder, Cole, 1977, pp. 151-163

Crossref

Google Scholar

[3]

B~.rtLmCAMP, E. Algebraic Coding Theory. McGraw-HilL New York, 1968.

Google Scholar

[4]

BLUM, M, CrlANDgA, A, AND WEOMAt~, M.Equivalence of free Boolean graphs can be decided probabthsticaUy m polynomial time. Inf. Prec. Lett 10 (1980), 80-82.

Google Scholar

[5]

CooK, S The complexity of theorem-proving procedures Prec. 3rd Ann, ACM Symp, on Theory of Computing, Shaker Heights, Ohio, 1971, pp 151-158.

Crossref

Google Scholar

[6]

GAREv, M, AND JOHNSON, D Computers and lntractabthty" A Guide to the Theory of NP-Corapletehess. Freeman, San Franosco, 1979.

Crossref

Google Scholar

[7]

HARDY, G, AND WRIGHT, E.The Theory of Numbers, 4th ed. Oxford University Press, 1960,

Google Scholar

[8]

HOeCROrT, J., Ar,rD ULL~t~,N, J.D. lntroductwn to Automata Theory, Languages and Computation. Addason-Wesley, Reading, Mass., 1979.

Crossref

Google Scholar

[9]

HYAFIL, L, On the parallel evaluation of multtvariate polynomials. Proe. lOth Ann. ACM Syrup, on Theory of Computing, San Diego, Calif., 1978, pp. 193-195.

Crossref

Google Scholar

[10]

InA~.x, O, AND Lma, aNcmR, B. On the simplification and equivalence problems for straight-line programs To appear in ~ ACM (available as Teeh. Rep. 79-21, Computer Science Dep., Univ. of Minnesota, Minneapolis, Minn., 1979).

Google Scholar

[11]

IB~a~tRA, O., Rosmr., L, A~qD MO~N, S.Probabilistie algorithms and stratght-hne programs for some rank de,asion problems. Inf Prec. Lett. 12 (1981), 227-232.

Google Scholar

[12]

KNtrrH, D.The Art of Computer Programming, Vol. 2. Seminumerical Algorithms. Addison-Wesley, Reading, Mass., 1969.

Google Scholar

[13]

MEYER, A, AND STOCKM~YER, L.Word problems reqmring exponential trine. Prec. 5th Ann. ACM Symp. on Theory of Computing, Austin, Texas, 1973, pp 1-9

Crossref

Google Scholar

[14]

MILLER, G.Raemann's hypothests and tests of primahty. Ph D. Dissertation, Umv. of California, Berkeley, Calif', 1975.

Google Scholar

[15]

MoR^I~, S.On the accepting dertstty hierarchy in NP (submitted for publication) A more complete versmn is available as Tech. Rep. 79-29, Computer Science Dep., Umv. of Minnesota, Minneapolis, Mitre, 1979.

Google Scholar

[16]

SCRWAgTZ, J.Fast probabihstic algorithms for venficatton of polynomial identities. ~ A CM 27, 4 (Oct. 1980), 701-717.

Crossref

Google Scholar

[17]

VALIArrr, L. Completeness classes m algebra. Proc. 1 lth Ann ACM Symp on Theory of Computing, Atlanta, Ga., 1979, pp. 249-261

Crossref

Google Scholar

[18]

YEMINt, Y.Some theoretical aspects of position-location problems. Prec. 20th Ann. IEEE Symp on Foundations of Computer Sctence, San Juan, Puerto Rico, 1979, pp. 1-8.

Google Scholar

[19]

YF.mNI, Y. On some randomly dectdable geometrical problems. Submitted for publicauon.

Google Scholar

Cited By

View all

Kommrusch SMonperrus MPouchet L(2023)Self-Supervised Learning to Prove Equivalence Between Straight-Line Programs via Rewrite RulesIEEE Transactions on Software Engineering10.1109/TSE.2023.327106549:7(3771-3792)Online publication date: 27-Apr-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3271065
Lohrey M(2021)Compression Techniques in Group TheoryConnecting with Computability10.1007/978-3-030-80049-9_30(330-341)Online publication date: 5-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-80049-9_30
Barth DBeck MDose TGlaßer CMichler LTechnau M(2020)Emptiness problems for integer circuitsTheoretical Computer Science10.1016/j.tcs.2020.03.023824-825(11-35)Online publication date: Jul-2020
https://doi.org/10.1016/j.tcs.2020.03.023
Show More Cited By

Index Terms

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation

Recommendations

Strong equivalence of logic programs under the infinite-valued semantics

We consider the notion of strong equivalence [V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526-541] of normal propositional logic programs under the infinite-valued ...
Inductive equivalence of logic programs
ILP'05: Proceedings of the 15th international conference on Inductive Logic Programming

This paper studies equivalence issues in inductive logic programming. A background theory B₁ is inductively equivalent to another background theory B₂ if B₁ and B₂ induce the same hypotheses for any given set of examples. Inductive equivalence is useful ...
Possibilistic nested logic programs and strong equivalence

In this paper, the class of possibilistic nested logic programs is introduced. These possibilistic logic programs allow us to use nested expressions in the bodies and heads of their rules. By considering a possibilistic nested logic program as a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 30, Issue 1

Jan. 1983

228 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322358

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1983

Published in JACM Volume 30, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
614
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)18

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kommrusch SMonperrus MPouchet L(2023)Self-Supervised Learning to Prove Equivalence Between Straight-Line Programs via Rewrite RulesIEEE Transactions on Software Engineering10.1109/TSE.2023.327106549:7(3771-3792)Online publication date: 27-Apr-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3271065
Lohrey M(2021)Compression Techniques in Group TheoryConnecting with Computability10.1007/978-3-030-80049-9_30(330-341)Online publication date: 5-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-80049-9_30
Barth DBeck MDose TGlaßer CMichler LTechnau M(2020)Emptiness problems for integer circuitsTheoretical Computer Science10.1016/j.tcs.2020.03.023824-825(11-35)Online publication date: Jul-2020
https://doi.org/10.1016/j.tcs.2020.03.023
Ganardi MHucke DKönig DLohrey M(2018)Circuits and Expressions over Finite SemiringsACM Transactions on Computation Theory10.1145/324137510:4(1-30)Online publication date: 28-Aug-2018
https://dl.acm.org/doi/10.1145/3241375
König DLohrey M(2018)Parallel identity testing for skew circuits with big powers and applicationsInternational Journal of Algebra and Computation10.1142/S021819671850043128:06(979-1004)Online publication date: Sep-2018
https://doi.org/10.1142/S0218196718500431
König DLohrey M(2018)Evaluation of Circuits Over Nilpotent and Polycyclic GroupsAlgorithmica10.1007/s00453-017-0343-z80:5(1459-1492)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0343-z
Lohrey MZetzsche G(2018)Knapsack in Graph GroupsTheory of Computing Systems10.1007/s00224-017-9808-362:1(192-246)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s00224-017-9808-3
Lohrey MSchmidt-Schauβ M(2017)Processing Succinct Matrices and VectorsTheory of Computing Systems10.1007/s00224-015-9666-961:2(322-351)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00224-015-9666-9
Mulmuley K(2016)Geometric complexity theory V: Efficient algorithms for Noether normalizationJournal of the American Mathematical Society10.1090/jams/86430:1(225-309)Online publication date: 21-Jun-2016
https://doi.org/10.1090/jams/864
Pardo LPardo M(2016)On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminantApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-016-0284-927:4(303-358)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s00200-016-0284-9
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Strong equivalence of logic programs under the infinite-valued semantics

Inductive equivalence of logic programs

Possibilistic nested logic programs and strong equivalence

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations