Fundamenta Informaticae - Volume 162, issue 2-3

Authors: Halava, Vesa | Karhumäki, Juhani | Matiyasevich, Yuri | Volkov, Mikhail

Article Type: Other

DOI: 10.3233/FI-2018-1715

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. i-i, 2018

Authors: Afonin, Sergey

Article Type: Research Article

Abstract: In this paper we summarize known results on decision problems for finitely generated semigroups and rational sets of regular languages and prove various statements on the topic. In particular, we prove undecidability of the equivalence problem for rational set of finite languages, automaticity of finitely generated semigroups of factorial languages, and provide an algorithm for automatic presentation construction in case of regular factorial languages. We also discuss possible direction for future research and describe applications of rational sets of regular languages to computer science problems.

Keywords: Rational set of regular languages, semigroup of regular languages, membership problem, automatic structure, factorial languages

DOI: 10.3233/FI-2018-1716

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 101-118, 2018

Authors: Guterman, Alexander E. | Maksaev, Artem M.

Article Type: Research Article

Abstract: The notion of scrambling index was firstly introduced by Akelbek and Kirkland in 2009. For a primitive digraph D , it is defined as the smallest positive integer k such that for every pair of vertices u and v of D there exist two directed paths of lengths k to a common vertex w . This notion turned out to be useful for several applications, e. g., to estimate eigenvalues of non-negative primitive stochastic matrices. In 2010 Huang and Liu with the background of a memoryless communication system generalized this notion to λ-tuples of vertices …and named it λ-th upper scrambling index. These notions can be reformulated in terms of matrix theory. A standard way to generate matrices with the given λ-th upper scrambling index is to apply certain matrix transformations that preserve this index to the existing examples of matrices with known λ-th upper scrambling index. In this paper we completely characterize bijective linear maps preserving λ-th upper scrambling index 1 or 0. Show more

Keywords: scrambling matrix, scrambling index, directed graphs, nonnegative matrices

DOI: 10.3233/FI-2018-1717

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 119-141, 2018

Authors: Hakanen, Anni | Laihonen, Tero

Article Type: Research Article

Abstract: A subset S of vertices is a resolving set in a graph if every vertex has a unique array of distances to the vertices of S . Consequently, we can locate any vertex of the graph with the aid of the distance arrays. The problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we consider sets S which can locate several, say up to ℓ, vertices in a graph. These sets are called {ℓ}-resolving sets and the smallest cardinality of such a set …is the {ℓ}-metric dimension of the graph. In this paper, we will give the {ℓ}-metric dimensions for trees and king grids. We will show that there are certain vertices that necessarily belong to an {ℓ}-resolving set. Moreover, we will classify all graphs whose {ℓ}-metric dimension equals ℓ. Show more

Keywords: Resolving set, metric dimension, metric basis, locating several vertices, forced vertices, king grid

DOI: 10.3233/FI-2018-1718

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 143-160, 2018

Authors: Ko, Sang-Ki | Potapov, Igor

Article Type: Research Article

Abstract: We study the vector ambiguity problem and the vector freeness problem in SL(2, ℤ). Given a finitely generated n × n matrix semigroup S and an n -dimensional vector x, the vector ambiguity problem is to decide whether for every target vector y = M x, where M ∈ S , M is unique. We also consider the vector freeness problem which is to show that every matrix M which is transforming x to M x has a unique factorization with respect to the generator of S . We show that both problems are …NP-complete in SL(2, ℤ), which is the set of 2 × 2 integer matrices with determinant 1. Moreover, we generalize the vector ambiguity problem and extend to the finite and k -vector ambiguity problems where we consider the degree of vector ambiguity of matrix semigroups. Show more

Keywords: matrix semigroup, special linear group, vector ambiguity, vector freeness, decidability, NP-completeness

DOI: 10.3233/FI-2018-1719

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 161-182, 2018

Authors: Maslennikova, Marina | Rodaro, Emanuele

Article Type: Research Article

Abstract: We follow language theoretic approach to synchronizing automata and Černý’s conjecture initiated in a series of recent papers. We prove that for every ideal language there exists a strongly connected synchronizing automaton from some special class for which given language serves as the language of reset words. This class is formed by trim automata recognizing left quotients of principal left ideal languages. We show that the minimal automaton recognizing a left quotient of a principal left ideal can be viewed as a synchronizing automaton for which given finitely generated ideal serves as the language of reset words.

Keywords: ideal language, synchronizing automaton, reset word, reset complexity, reset left regular decomposition, strongly connected automaton

DOI: 10.3233/FI-2018-1720

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 183-203, 2018

Authors: Ryzhikov, Andrew | Shemyakov, Anton

Article Type: Research Article

Abstract: We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general automata can be solved in polynomial time in monotonic automata, even without knowing a linear order of the states preserved by the transitions. We provide asymptotically tight bounds on the maximum length of a shortest word synchronizing a subset of states in a monotonic automaton and a shortest word carefully synchronizing a partial monotonic automaton. We provide a complexity framework for dealing with problems for monotonic weakly acyclic automata over a three-letter alphabet, and use …it to prove NP-completeness and inapproximability of problems such as FINITE AUTOMATA INTERSECTION and the problem of computing the rank of a subset of states in this class. We also show that checking whether a monotonic partial automaton over a four-letter alphabet is carefully synchronizing is NP-hard. Finally, we give a simple necessary and sufficient condition when a strongly connected digraph with a selected subset of vertices can be transformed into a deterministic automaton where the corresponding subset of states is synchronizing. Show more

Keywords: Synchronizing automaton, subset synchronization, careful synchronization, monotonic automaton

DOI: 10.3233/FI-2018-1721

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 205-221, 2018

Authors: Saarela, Aleksi

Article Type: Research Article

Abstract: We briefly survey some results and open problems on word equations, especially on those equations where the right-hand side is a power of a variable. We discuss a method that was recently used to prove one of the results, and we prove improved versions of some lemmas that are related to the method and can be used as tools when studying word equations. We use the method and the tools to give new, simple proofs for several old results.

DOI: 10.3233/FI-2018-1722

Citation: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 223-235, 2018