Ke Yang

In this paper, we address the problem of evaluating the

Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over

the set of natural numbers. The problem is a natural extension

to the integer expression by Stockmeyer and Mayer, and is also studied

by Mckenzie, Vollmer and Wagner in ...
more >>>

Titus Dose

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits

computing finite sets of natural numbers. These problems naturally build on problems for integer

expressions and integer circuits studied by Stockmeyer and Meyer (1973),

McKenzie and Wagner (2007),

and Glaßer et al (2010).

Our work shows that the ... more >>>