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

DOI10.1137/0211002zbMath0481.68026OpenAlexW2034269421MaRDI QIDQ3939215

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) Undecidability and degrees of sets of sentences (03D35) 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)

Related Items (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