Fundamenta Informaticae - Volume 179, issue 4

Authors: Bergstra, J.A. | Middelburg, C.A.

Article Type: Research Article

Abstract: This paper concerns the relation between process algebra and Hoare logic. We investigate the question whether and how a Hoare logic can be used for reasoning about how data change in the course of a process when reasoning equationally about that process. We introduce an extension of ACP (Algebra of Communicating Processes) with features that are relevant to processes in which data are involved, present a Hoare logic for the processes considered in this process algebra, and discuss the use of this Hoare logic as a complement to pure equational reasoning with the equational axioms of the process algebra.

Keywords: process algebra, data parameterized action, assignment action, guarded command, asserted process, Hoare logic

DOI: 10.3233/FI-2021-2026

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

Authors: Boomari, Hossein | Ostovari, Mojtaba | Zarei, Alireza

Article Type: Research Article

Abstract: A Triangulated Irregular Network (TIN) is a data structure that is usually used for representing and storing monotone geographic surfaces, approximately. In this representation, the surface is approximated by a set of triangular faces whose projection on the XY -plane is a triangulation. The visibility graph of a TIN is a graph whose vertices correspond to the vertices of the TIN and there is an edge between two vertices if their corresponding vertices on TIN see each other, i.e. the segment that connects these vertices completely lies above the TIN . Computing the visibility graph …of a TIN and its properties have been considered thoroughly in the literature. In this paper, we consider this problem in reverse: Given a graph G , is there a TIN with the same visibility graph as G ? We show that this problem is ∃ℝ-Complete . Show more

Keywords: Visibility graph triangulated irregular network recognizing visibility graph existential theory of the reals

DOI: 10.3233/FI-2021-2027

Citation: Fundamenta Informaticae, vol. 179, no. 4, pp. 345-360, 2021

Authors: Křivka, Zbyněk | Meduna, Alexander

Article Type: Research Article

Abstract: This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

Keywords: Scattered context grammars, size reduction, the number of non-context-free productions, parallel productions, computational completeness, descriptional complexity

DOI: 10.3233/FI-2021-2028

Citation: Fundamenta Informaticae, vol. 179, no. 4, pp. 361-384, 2021

Authors: Teh, Wen Chean | Atanasiu, Adrian | Wong, Denis C.K.

Article Type: Research Article

Abstract: Since the undecidability of the mortality problem for 3 × 3 matrices over integers was proved using the Post Correspondence Problem, various studies on decision problems of matrix semigroups have emerged. The freeness problem in particular has received much attention but decidability remains open even for 2 × 2 upper triangular matrices over nonnegative integers. Parikh matrices are upper triangular matrices introduced as a generalization of Parikh vectors and have become useful tools in studying of subword occurrences. In this work, we focus on semigroups of Parikh matrices and study the freeness problem in this context.

Keywords: Freeness problem, matrix semigroups, Parikh matrices, decidability

DOI: 10.3233/FI-2021-2029

Citation: Fundamenta Informaticae, vol. 179, no. 4, pp. 385-397, 2021

Authors: Wang, Zhaohao

Article Type: Research Article

Abstract: Matroid theory is a useful tool for the combinatorial optimization issue in data mining, machine learning and knowledge discovery. Recently, combining matroid theory with rough sets is becoming interesting. In this paper, rough set approaches are used to investigate an important class of matroids, transversal matroids. We first extend the concept of upper approximation number functions in rough set theory and propose the notion of generalized upper approximation number functions on a set system. By means of the new notion, we give some necessary and sufficient conditions for a subset to be a partial transversal of a set system. Furthermore, …we obtain a new description of a transversal matroid by the generalized upper approximation number function. We show that a transversal matroid can be induced by the generalized upper approximation number function which can be decomposed into the sum of some elementary generalized upper approximation number functions. Conversely, we also prove that a generalized upper approximation number function can induce a transversal matroid. Finally, we apply the generalized upper approximation number function to study the relationship among transversal matroids. Show more

Keywords: Matroid, Rough set, Approximation number function, Set system, Multset

DOI: 10.3233/FI-2021-2030

Citation: Fundamenta Informaticae, vol. 179, no. 4, pp. 399-416, 2021