Fundamenta Informaticae - Volume 172, issue 1

Authors: Brodo, Linda | Olarte, Carlos

Article Type: Research Article

Abstract: The Core Network Algebra (CNA) is a model for concurrency that extends the point-to-point communication discipline of Milner’s CCS with multiparty interactions. Links are used to build chains describing how information flows among the different agents participating in a multiparty interaction. The inherent non-determinism in deciding both the number of participants in an interaction, and how they synchronize, makes it difficult to devise verification techniques for this language. We propose a symbolic semantics and a symbolic bisimulation for CNA which are more amenable for automating reasoning. Unlike the operational semantics of CNA, the symbolic semantics is finitely branching and it …represents, compactly, a possibly infinite number of transitions. We give necessary and sufficient conditions to efficiently check the validity of symbolic configurations. We also propose the Symbolic Link Modal Logic, a seamless extension of the Hennessy-Milner logic which is able to characterize the (symbolic) transitions of CNA processes. Finally, we specify both the symbolic semantics and the modal logic as an executable rewriting theory. We thus obtain several verification procedures to analyze CNA processes. Show more

Keywords: Concurrency theory, process calculi, CCS, symbolic semantics, verification

DOI: 10.3233/FI-2020-1890

Citation: Fundamenta Informaticae, vol. 172, no. 1, pp. 1-38, 2020

Authors: Hittmeir, Markus | Pomykała, Jacek

Article Type: Research Article

Abstract: In this paper, we construct deterministic factorization algorithms for natural numbers N under the assumption that the prime power decomposition of Euler’s totient function φ (N ) is known. Their runtime complexities depend on the number ω (N ) of distinct prime divisors of N , and we present efficient methods for relatively small values of ω (N ) as well as for its large values. One of our main goals is to establish an asymptotic expression with explicit remainder term O (x /A ) for the number of positive integers N ≤ x composed of s …distinct prime factors that can be factored nontrivially in deterministic time t = t (x ), provided that the prime power decomposition of φ (N ) is known. We obtain it for A = A (x ) = x 1–ɛ , where ɛ = ɛ (s ) > 0 is sufficiently small and t = t (x ) is a polynomial in log x of degree d = d (ɛ ). An analogous bound is deduced under the assumption of the oracle providing the decomposition of orders of elements in ℤ N * . Show more

Keywords: Factorization, Totient Function, Deterministic Reduction

DOI: 10.3233/FI-2020-1891

Citation: Fundamenta Informaticae, vol. 172, no. 1, pp. 39-51, 2020

Authors: Paul, Prithwineel

Article Type: Research Article

Abstract: In this work we initiate the study of Szilard languages of labelled insertion grammars. It is well-known that there exist context-free languages which cannot be generated by any insertion grammar. We show that there exist some regular languages which cannot be Szilard language of any labelled insertion grammar. But any regular language can be given as a homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 1. Also, any context-free language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2. We show that even though insertion grammars …of weight 1 can generate only context-free languages, there exists some context-sensitive language which can be obtained as Szilard language of a labelled insertion grammar of weight 1. At the end we show that any recursively enumerable language can be characterized by the homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 5. Show more

Keywords: Insertion grammar, Szilard languages, Labelled insertion grammar, Chomsky hierarchy

DOI: 10.3233/FI-2020-1892

Citation: Fundamenta Informaticae, vol. 172, no. 1, pp. 53-72, 2020

Authors: Polkowski, Lech

Article Type: Research Article

Abstract: Continuing our work on mass-based rough mereologies, we make use of the Stone representation theorem for complete Boolean algebras and we exhibit the existence of a finite base in each mereological space. Those bases in turn allow for the introduction of distributed mereologies; regarding each element of the base as a mereological space, we propose a mechanism for fusing those mereological spaces into a global distributed mereological space. We define distributed mass-assignments and rough inclusions pointing to possible applications.

Keywords: mereology, rough mereology, rough inclusion, mass assignment, Stone representation, Stone space, the compactness theorem, distributed mereology

DOI: 10.3233/FI-2020-1893

Citation: Fundamenta Informaticae, vol. 172, no. 1, pp. 73-95, 2020

Authors: Raghu, T. Venkata | Sundara Rajan, R. | Ramesh Babu, A. | Anil, S.

Article Type: Research Article

Abstract: A subset S of a connected graph G of order n is called a detour set of G if for every vertex x in G there exist vertices u ; v in S such that x lie on a u – v detour path. The detour number dn (G ) of a graph G is the minimum cardinality of a detour set. In this paper we compute the detour number of certain 1-fault connected planar graphs.

Keywords: Geodetic number, detour set, detour number, 1-fault connected graphs, Hanoi graph, Sierpiński graph

DOI: 10.3233/FI-2020-1894

Citation: Fundamenta Informaticae, vol. 172, no. 1, pp. 97-104, 2020