Fundamenta Informaticae - Volume 181, issue 4

Authors: van der Aalst, Wil M.P.

Article Type: Research Article

Abstract: A marked Petri net is lucent if there are no two different reachable markings enabling the same set of transitions, i.e., states are fully characterized by the transitions they enable. Characterizing the class of systems that are lucent is a foundational and also challenging question. However, little research has been done on the topic. In this paper, it is shown that all free-choice nets having a home cluster are lucent. These nets have a so-called home marking such that it is always possible to reach this marking again. Such a home marking can serve as a regeneration point …or as an end-point. The result is highly relevant because in many applications, we want the system to be lucent and many “well-behaved” process models fall into the class identified in this paper. Unlike previous work, we do not require the marked Petri net to be live and stronglyconnected. Most of the analysis techniques for free-choice nets are tailored towards well-formed nets. The approach presented in this paper provides a novel perspective enabling new analysis techniques for free-choice nets that do not need to be well-formed. Therefore, we can also model systems and processes that are terminating and/or have an initialization phase. Show more

Keywords: Petri nets, Free-Choice Nets, Lucent Process Models

DOI: 10.3233/FI-2021-2059

Citation: Fundamenta Informaticae, vol. 181, no. 4, pp. 273-302, 2021

Authors: Dryło, Robert

Article Type: Research Article

Abstract: Formulas for doubling, differential addition and point recovery after compression were given for many standard models of elliptic curves, and allow for scalar multiplication after compression using the Montgomery ladder algorithm and point recovery on a curve after this multiplication. In this paper we give such formulas for the twisted Jacobi intersection au 2 + v 2 = 1, bu 2 + w 2 = 1. To our knowledge such formulas were not given for this model or for the Jacobi intersection. In projective coordinates these formulas have cost 2M +2S +6D for …doubling and 5M + 2S + 6D for differential addition, where M ; S ; D are multiplication, squaring and multiplication by constants in a field, respectively, choosing suitable curve parameters cost of D may be small. Show more

Keywords: elliptic curve cryptography, point compression on elliptic curves, the Montgomery ladder algorithm, the twisted Jacobi intersection

DOI: 10.3233/FI-2021-2060

Citation: Fundamenta Informaticae, vol. 181, no. 4, pp. 303-312, 2021

Authors: Pérez, Claudia | Rivera, Daniel

Article Type: Research Article

Abstract: Skew-symmetrizable matrices play an essential role in the classification of cluster algebras. We prove that the problem of assigning a positive definite quasi-Cartan companion to a skew-symmetrizable matrix is in polynomial class P. We also present an algorithm to determine the finite type Δ ∈ {𝔸n ; 𝔻n ; 𝔹n ; ℂn ; 𝔼6 ; 𝔼7 ; 𝔼8 ; 𝔽4 ; 𝔾2 } of a cluster algebra associated to the mutation-equivalence class of a connected skew-symmetrizable matrix B , if it has one.

Keywords: Cluster algebra, positive quasi-Cartan companion, polynomial algorithm, biconnected component, triconnected component

DOI: 10.3233/FI-2021-2061

Citation: Fundamenta Informaticae, vol. 181, no. 4, pp. 313-337, 2021

Authors: Zhang, Kuize

Article Type: Research Article

Abstract: The state detection problem and fault diagnosis/prediction problem are fundamental topics in many areas. In this paper, we consider discrete-event systems (DESs) modeled by finite-state automata (FSAs). There exist plenty of results on decentralized versions of the latter problem but there is almost no result for a decentralized version of the former problem. In this paper, we propose a decentralized version of strong detectability called co-detectability which means that if a system satisfies this property, for each generated infinite-length event sequence, in at least one location the current and subsequent states can be determined by observations in the location …after a common observation time delay. We prove that the problem of verifying co-detectability of deterministic FSAs is coNP-hard. Moreover, we use a unified concurrent-composition method to give PSPACE verification algorithms for co-detectability, co-diagnosability, and co-predictability of FSAs, without any assumption on or modification of the FSAs under consideration, where co-diagnosability is first studied by [Debouk & Lafortune & Teneketzis 2000], co-predictability is first studied by [Kumar & Takai 2010]. By our proposed unified method, one can see that in order to verify co-detectability, more technical difficulties will be met compared with verifying the other two properties, because in co-detectability, generated outputs are counted, but in the latter two properties, only occurrences of events are counted. For example, when one output was generated, any number of unobservable events could have occurred. PSPACE-hardness of verifying co-diagnosability is already known in the literature. In this paper, we prove PSPACE-hardness of verifying co-predictability. Show more

Keywords: discrete-event system, finite-state automaton, co-detectability, co-diagnosability, co-predictability, concurrent composition, complexity

DOI: 10.3233/FI-2021-2062

Citation: Fundamenta Informaticae, vol. 181, no. 4, pp. 339-371, 2021