The Complexity of the Equivalence Problem for Simple Loop-Free Programs

DOI10.1137/0211002MaRDI QIDQ3939215zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Brian S. Leininger

Publication date 1982

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0211002

zbMATH Keywords

complexityequivalenceNP-hardzero-equivalenceloop-free program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35)

Cited in

(2)

• On the complexity of commutativity analysis
• On the complexity of simple arithmetic expressions

This page was built for publication: The Complexity of the Equivalence Problem for Simple Loop-Free Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3939215)