Reversible computations constitute an unconventional form of computing where
any sequence of performed operations can be undone by executing in reverse
order at any point during a computation. It has been attracting increasing
attention as it provides opportunities for low-power computation, being at the
same time essential or eligible in various applications. In recent work, we
have proposed a structural way of translating Reversing Petri Nets (RPNs) - a
type of Petri nets that embeds reversible computation, to bounded Coloured
Petri Nets (CPNs) - an extension of traditional Petri Nets, where tokens carry
data values. Three reversing semantics are possible in RPNs: backtracking
(reversing of the lately executed action), causal reversing (action can be
reversed only when all its effects have been undone) and out of causal
reversing (any previously performed action can be reversed). In this paper, we
extend the RPN to CPN translation with formal proofs of correctness. Moreover,
the possibility of introduction of cycles to RPNs is discussed. We analyze
which type of cycles could be allowed in RPNs to ensure consistency with the
current semantics. It emerged that the most interesting case related to cycles
in RPNs occurs in causal semantics, where various interpretations of dependency
result in different net's behaviour during reversing. Three definitions of
dependence are presented and discussed.
This paper presents algorithms for computing the length of a sum of squares
and a Pythagoras element in a global field $K$ of characteristic different from
$2$. In the first part of the paper, we present algorithms for computing the
length in a non-dyadic and dyadic (if $K$ is a number field) completion of $K$.
These two algorithms serve as subsidiary steps for computing lengths in global
fields. In the second part of the paper we present a procedure for constructing
an element whose length equals the Pythagoras number of a global field, termed
a Pythagoras element.
Recently, an interest in constructing pseudorandom or hitting set generators
for restricted branching programs has increased, which is motivated by the
fundamental issue of derandomizing space-bounded computations. Such
constructions have been known only in the case of width 2 and in very
restricted cases of bounded width. In this paper, we characterize the hitting
sets for read-once branching programs of width 3 by a so-called richness
condition. Namely, we show that such sets hit the class of read-once
conjunctions of DNF and CNF (i.e. the weak richness). Moreover, we prove that
any rich set extended with all strings within Hamming distance of 3 is a
hitting set for read-once branching programs of width 3. Then, we show that any
almost $O(\log n)$-wise independent set satisfies the richness condition. By
using such a set due to Alon et al. (1992) our result provides an explicit
polynomial-time construction of a hitting set for read-once branching programs
of width 3 with acceptance probability $\varepsilon>5/6$. We announced this
result at conferences more than ten years ago, including only proof sketches,
which motivated a number of subsequent results on pseudorandom generators for
restricted read-once branching programs. This paper contains our original
detailed proof that has not been published yet.