Fundamenta Informaticae - Volume 191, issue 3-4

Authors: Halava, Vesa | Kari, Jarkko | Laihonen, Tero

Article Type: Editorial

DOI: 10.3233/FI-242177

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. i-i, 2024

Authors: Hudry, Olivier | Ville, Junnila | Lobstein, Antoine

Article Type: Research Article

Abstract: A set C of vertices in a graph G = (V , E ) is an identifying code if it is dominating and any two vertices of V are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala’s contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes.

Keywords: graph theory, combinatorics, identifying codes, domination, separation, twin-free graphs, complexity, binary Hamming spaces, infinite grids, classic parameters of graphs, number of optimal solutions

DOI: 10.3233/FI-242178

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 165-196, 2024

Authors: Chakraborty, Dipayan | Foucaud, Florent | Parreau, Aline | Wagler, Annegret

Article Type: Research Article

Abstract: The problems of determining the minimum-sized identifying , locating-dominating and open locating-dominating codes of an input graph are special search problems that are challenging from both theoretical and computational viewpoints. In these problems, one selects a dominating set C of a graph G such that the vertices of a chosen subset of V (G ) (i.e. either V (G ) \ C or V (G ) itself) are uniquely determined by their neighborhoods in C . A typical line of attack for these problems is to determine tight bounds for the minimum codes in various …graph classes. In this work, we present tight lower and upper bounds for all three types of codes for block graphs (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or blocks ) of a block graph and the order of the graph. Two of our upper bounds verify conjectures from the literature with one of them being now proven for block graphs in this article. As for the lower bounds, we prove them to be linear in terms of both the number of blocks and the order of the block graph. We provide examples of families of block graphs whose minimum codes attain these bounds, thus showing each bound to be tight. Show more

Keywords: identifying code, locating-dominating code, open locating-dominating code, block graph

DOI: 10.3233/FI-242179

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 197-229, 2024

Authors: Salomaa, Arto | Salomaa, Kai | Smith, Taylor J.

Article Type: Research Article

Abstract: The state complexity, respectively, nondeterministic state complexity of a regular language L is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for L . Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a …regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable. Show more

Keywords: finite automaton, state complexity, degree of ambiguity, regularity preserving operation, undecidability

DOI: 10.3233/FI-242180

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 231-237, 2024

Authors: Auger, David | Cohen, Johanne | Lobstein, Antoine

Article Type: Research Article

Abstract: We introduce a game where players selfishly choose a resource and endure a cost depending on the number of players choosing nearby resources. We model the influences among resources by a weighted graph, directed or not. These games are generalizations of well-known games like Wardrop and congestion games. We study the conditions of equilibria existence and their efficiency if they exist. We conclude with studies of games whose influences among resources can be modelled by simple graphs.

Keywords: Neighbourhood Balancing Games, Nash equilibrium, graph theory

DOI: 10.3233/FI-242181

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 239-268, 2024

Authors: Halava, Vesa | Harju, Tero | Nowotka, Dirk | Sahla, Esa

Article Type: Research Article

Abstract: We study decision problems of the form: given a regular or linear context-free language L , is there a word of a given fixed form in L , where given fixed forms are based on word operations copy, marked copy, shuffle and their combinations.

Keywords: Regular language, linear context-free language, shuffle, marked copy, reverse copy, membership problem

DOI: 10.3233/FI-242182

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 269-284, 2024

Authors: Honkala, Juha

Article Type: Research Article

Abstract: A morphism g from the free monoid X * into itself is called upper triangular if the matrix of g is upper triangular. We characterize all upper triangular binary morphisms g 1 and g 2 such that g 1 g 2 = g 2 g 1 .

Keywords: Free monoid morphism, Commutativity, Combinatorics on morphisms

DOI: 10.3233/FI-242183

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 285-298, 2024

Authors: Gustafsson, Patric | Petre, Ion

Article Type: Research Article

Abstract: Logical modeling is a powerful tool in biology, offering a system-level understanding of the complex interactions that govern biological processes. A gap that hinders the scalability of logical models is the need to specify the update function of every vertex in the network depending on the status of its predecessors. To address this, we introduce in this paper the concept of strong regulation, where a vertex is only updated to active/inactive if all its predecessors agree in their influences; otherwise, it is set to ambiguous. We explore the interplay between active, inactive, and ambiguous influences in a network. We discuss …the existence of phenotype attractors in such networks, where the status of some of the variables is fixed to active/inactive, while the others can have an arbitrary status, including ambiguous. Show more

Keywords: Biomodeling, interaction networks, regulatory graphs, Boolean networks, phenotype attractors

DOI: 10.3233/FI-242184

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 299-314, 2024

Authors: Hakanen, Anni | Yero, Ismael G.

Article Type: Research Article

Abstract: This investigation is firstly focused into showing that two metric parameters represent the same object in graph theory. That is, we prove that the multiset resolving sets and the ID-colorings of graphs are the same thing. We also consider some computational and combinatorial problems of the multiset dimension, or equivalently, the ID-number of graphs. We prove that the decision problem concerning finding the multiset dimension of graphs is NP-complete. We consider the multiset dimension of king grids and prove that it is bounded above by 4. We also give a characterization of the strong product graphs with one factor being …a complete graph, and whose multiset dimension is not infinite. Show more

Keywords: multiset resolving set, multiset dimension, ID-colorings, ID-number, king grids

DOI: 10.3233/FI-242185

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 315-330, 2024

Authors: Salo, Ville | Törmä, Ilkka

Article Type: Research Article

Abstract: We apply automata theory and Karp’s minimum mean weight cycle algorithm to minimum density problems in coding theory. Using this method, we find the new upper bound 53/126 ≈ 0.4206 for the minimum density of an identifying code on the infinite hexagonal grid, down from the previous record of 3/7 ≈ 0.4286.

Keywords: identifying code, coding theory, minimal density

DOI: 10.3233/FI-242186

Citation: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 331-349, 2024