Conditional Expressions with Equality Tests

Ravi Sethi

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Condmonal expressions of the form “if E=F then G else H,” where E,F,G,H may themselves be such expressions, have long been used to describe the semantics of assignments. We consider the problem of deciding if two nested condmonals of the above form compute the same values Three transformahons are used to solve the problem A dtstrtbutwe transformation converts any conditional to the sampler form if A =B then G else H, where A and B are variables rather than expressions. An trnphed test transformation finds all tests in subexpresslons whose outcome as Jmphed by prevtous tests. Finally, the useless test transformation is used to reduce expressions of the form if A= B then C else C to C When all tests are between variables and the expressions are represented by trees, then equivalence of expressions can be tested in polynomial time The remaining cases have been shown elsewhere to be NP-hard.

Original languageEnglish (US)
Pages (from-to)667-674
Number of pages8
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Oct 1 1978


  • conditional expressions
  • emantics of assignment
  • equality predicate
  • expression simplification
  • program verification

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Conditional Expressions with Equality Tests'. Together they form a unique fingerprint.

Cite this