Fundamenta Informaticae - Volume 178, issue 3

Authors: Adinayev, Arthur | Stein, Itamar

Article Type: Research Article

Abstract: In this paper, we study a certain case of a subgraph isomorphism problem. We consider the Hasse diagram of the lattice Mk (the unique lattice with k + 2 elements and one anti-chain of length k ) and find the maximal k for which it is isomorphic to a subgraph of the reduction graph of a given one-rule string rewriting system. We obtain a complete characterization for this problem and show that there is a dichotomy. There are one-rule string rewriting systems for which the maximal such k is 2 and there are cases where …there is no maximum. No other intermediate option is possible. Show more

Keywords: one-rule string rewriting systems, reduction graph, subgraph isomorphism problem

DOI: 10.3233/FI-2021-2002

Citation: Fundamenta Informaticae, vol. 178, no. 3, pp. 173-185, 2021

Authors: Arockiaraj, Micheal | Delaila, J. Nancy | Abraham, Jessie

Article Type: Research Article

Abstract: In any interconnection network, task allocation plays a major role in the processor speed as fair distribution leads to enhanced performance. Complete multipartite networks serve well for this purpose as the task can be split into different partites which improves the degree of reliability of the network. Such an allocation process in the network can be done by means of graph embedding. The optimal wirelength of a graph embedding helps in the distribution of deterministic algorithms from the guest graph to other host graphs in order to incorporate its unique deterministic properties on that chosen graph. In this paper, we …propose an algorithm to compute the optimal wirelength of balanced complete multipartite graphs onto the Cartesian product of trees with path and cycle. Moreover, we derive the closed formulae for wirelengths in specific trees like (1-rooted) complete binary tree and sibling graphs. Show more

Keywords: Balanced complete t-partite graph, embedding, wirelength, Cartesian product

DOI: 10.3233/FI-2021-2003

Citation: Fundamenta Informaticae, vol. 178, no. 3, pp. 187-202, 2021

Authors: Jastrzab, Tomasz | Czech, Zbigniew J. | Wieczorek, Wojciech

Article Type: Research Article

Abstract: The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of …inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard. Show more

Keywords: parallel algorithms, learning regular languages using nondeterministic finite automata, constraint satisfaction and satisfiability problems, grammatical inference

DOI: 10.3233/FI-2021-2004

Citation: Fundamenta Informaticae, vol. 178, no. 3, pp. 203-227, 2021

Authors: Lanese, Ivan | Palacios, Adrián | Vidal, Germán

Article Type: Research Article

Abstract: Causal-consistent reversible debugging is an innovative technique for debugging concurrent systems. It allows one to go back in the execution focusing on the actions that most likely caused a visible misbehavior. When such an action is selected, the debugger undoes it, including all and only its consequences. This operation is called a causal-consistent rollback. In this way, the user can avoid being distracted by the actions of other, unrelated processes. In this work, we introduce its dual notion: causal-consistent replay . We allow the user to record an execution of a running program and, in contrast to traditional replay …debuggers, to reproduce a visible misbehavior inside the debugger including all and only its causes. Furthermore, we present a unified framework that combines both causal-consistent replay and causal-consistent rollback. Although most of the ideas that we present are rather general, we focus on a popular functional and concurrent programming language based on message passing: Erlang. Show more

Keywords: concurrency, logging, causal-consistent, debugging, reversible computing

DOI: 10.3233/FI-2021-2005

Citation: Fundamenta Informaticae, vol. 178, no. 3, pp. 229-266, 2021

Authors: Neethu, P. K. | Chandran, S.V. Ullas | Changat, Manoj | Klavžar, Sandi

Article Type: Research Article

Abstract: The general position number gp(G ) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S . The complementary prism G G ¯ of G is the graph formed from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. It is proved that gp(G G ¯ ) ≤ n (G ) + 1 …if G is connected and gp(G G ¯ ) ≤ n (G ) if G is disconnected. Graphs G for which gp(G G ¯ ) = n (G ) + 1 holds, provided that both G and G ¯ are connected, are characterized. A sharp lower bound on gp(G G ¯ ) is proved. If G is a connected bipartite graph or a split graph then gp(G G ¯ ) ∈ {n (G ), n (G )+1}. Connected bipartite graphs and block graphs for which gp(G G ¯ ) = n (G ) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order. Show more

Keywords: general position set, complementary prism, bipartite graph, split graph, block graph

DOI: 10.3233/FI-2021-2006

Citation: Fundamenta Informaticae, vol. 178, no. 3, pp. 267-281, 2021