Fundamenta Informaticae - Volume 182, issue 4

Authors: Zhengwei, Xie | Daowen, Qiu | Guangya, Cai | Gruska, Jozef | Mateus, Paulo

Article Type: Research Article

Abstract: The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ɛ -far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function f , of n variables, is identical with a given function g or is ɛ -far from g , where ɛ …is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O ( 1 ε ) . Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ ( 1 ε ) . Secondly, we consider the D-J problem from the perspective of functional correlations and let C (f , g ) denote the correlation of f and g . We propose an exact quantum algorithm for making distinction between |C (f , g )| = ɛ and |C (f , g )| = 1 using six queries, while the classical deterministic query complexity for this problem is Θ(2n ) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ɛ -far balanced using O ( 1 ε ) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O (1/ɛ 2 ). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Show more

Keywords: Deutsch-Jozsa Algorithm, Quantum amplitude amplification, Identity testing, Correlation testing, Balancedness testing

DOI: 10.3233/FI-2021-2076

Citation: Fundamenta Informaticae, vol. 182, no. 4, pp. 321-344, 2021

Authors: Sureson, Claude

Article Type: Research Article

Abstract: We propose a detailed proof of the fact that the inverse of Ackermann function is computable in linear time.

Keywords: Recursive functions, Complexity of computation

DOI: 10.3233/FI-2021-2077

Citation: Fundamenta Informaticae, vol. 182, no. 4, pp. 345-361, 2021

Authors: Wehler, Joachim

Article Type: Research Article

Abstract: Van der Aalst’s theorem is an important result for the analysis and synthesis of process models. The paper proves the theorem by exhausting perpetual free-choice Petri nets by CP -subnets. The resulting T -systems are investigated by elementary methods.

Keywords: Free-choice system, CP-subnet, perpetuality, lucency

DOI: 10.3233/FI-2021-2078

Citation: Fundamenta Informaticae, vol. 182, no. 4, pp. 363-393, 2021