Fundamenta Informaticae - Volume 184, issue 4

Authors: Barylska, Kamila | Gogolińska, Anna

Article Type: Research Article

Abstract: 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. Show more

DOI: 10.3233/FI-2021-2099

Citation: Fundamenta Informaticae, vol. 184, no. 4, pp. 273-296, 2021

Authors: Darkey-Mensah, Mawunyo Kofi | Rothkegel, Beata

Article Type: Research Article

Abstract: 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.

Keywords: Algorithms, Quadratic forms, Global fields, Length, Sum of squares, Pythagoras number, Pythagoras element, MSC: 11Y16, 11E12

DOI: 10.3233/FI-2021-2100

Citation: Fundamenta Informaticae, vol. 184, no. 4, pp. 297-306, 2021

Authors: Šíma, Jiří | Žák, Stanislav

Article Type: Research Article

Abstract: 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 ɛ > 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. Show more

Keywords: derandomization, hitting set, read-once branching program, bounded width, almost k-wise independent set

DOI: 10.3233/FI-2021-2101

Citation: Fundamenta Informaticae, vol. 184, no. 4, pp. 307-354, 2021