# Questions tagged [equivalence]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
84 views

### Is equivalence of uniform AC0 decidable?

Is there a representation of the functions from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ for which equivalence is decidable? Since the languages defined by nondeterministic pushdown automata ...
245 views

### Program equivalence wherein the programs are known to always halt

Say I have two programs with possibly infinite state spaces and some oracle has asserted that they both always halt. Can I always decide if they're contextually equivalent? If yes, is there a known ...
925 views

### Is iszero of the untyped lambda calculus sound and complete? [closed]

I am using the following definitions in the notation of Haskell. In case it matters, I would like to use only the $\alpha,\beta,\eta$ reductions rather than the Haskell evaluation rules. ...
137 views

### Why are these two definitions of PLS equivalent?

In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm. there is a ...
43 views

### Equilvalence among two Scheduling problems

I have two problems for scheduling: Packets arrive at a router. Router schedules them i.e. router determines which one will go out first and which one last. Here, the problem is which packet to send ...
132 views

### Are the ArrowApply and Monad typeclasses equivalent?

It is stated e.g. on Hackage, that the ArrowApply and the Monad typeclasses are equivalent. I have my doubts about this. It is ...
171 views

### What's the complexity of recognizing equivalence for the following relation?

Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers. We say that two matrices $A$, $B \in \mathcal{M}_{m,n}(\mathbb{Z})$ are equivalent if $A$ can be obtained ...
133 views