Fundamenta Informaticae - Volume 116, issue 1-4

Authors: Halava, Vesa | Karhumäki, Juhani | Nowotka, Dirk | Rozenberg, Grzegorz

Article Type: Other

DOI: 10.3233/FI-2012-662

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. vii-viii, 2012

Authors: Bell, Paul C. | Potapov, Igor

Article Type: Research Article

Abstract: Most computational problems for matrix semigroups and groups are inherently difficult to solve and even undecidable starting from dimension three. The questions about the decidability and complexity of problems for two-dimensional matrix semigroups remain open and are directly linked with other challenging problems in the field. In this paper we study the computational complexity of the problem of determining whether the identity matrix belongs to a matrix semigroup (the Identity Problem) generated by a finite set of 2 × 2 integral unimodular matrices. The Identity Problem for matrix semigroups is a well-known challenging problem, which has remained open in any …dimension until recently. It is currently known that the problem is decidable in dimension two and undecidable starting from dimension four. In particular, we show that the Identity Problem for 2 × 2 integral unimodular matrices is NP-hard by a reduction of the Subset Sum Problem and several new encoding techniques. An upper bound for the nontrivial decidability result by C. Choffrut and J. Karhumäki is unknown. However, we derive a lower bound on the minimum length solution to the Identity Problem for a constructible set of instances, which is exponential in the number of matrices of the generator set and the maximal element of the matrices. This shows that the most obvious candidate for an NP algorithm, which is to guess the shortest sequence of matrices which multiply to give the identity matrix, does not work correctly since the certificate would have a length which is exponential in the size of the instance. Both results lead to a number of corollaries confirming the same bounds for vector reachability, scalar reachability and zero in the right upper corner problems. Show more

DOI: 10.3233/FI-2012-663

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 1-13, 2012

Authors: Brijder, Robert | Hoogeboom, Hendrik Jan

Article Type: Research Article

Abstract: We consider the Schur complement operation for symmetric matrices over GF(2), which we identify with graphs through the adjacency matrix representation. It is known that Schur complementation for such a matrix (i.e., for a graph) can be decomposed into a sequence of two types of elementary Schur complement operations: (1) local complementation on a looped vertex followed by deletion of that vertex and (2) edge complementation on an edge without looped vertices followed by deletion of that edge. We characterize the symmetric matrices over GF(2) that can be transformed into the empty matrix using only operations of (1). As a …consequence, we find that these matrices can be inverted using local complementation. The result is applied to the theory of gene assembly in ciliates. Show more

DOI: 10.3233/FI-2012-664

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 15-23, 2012

Authors: Bucci, Michelangelo | De Luca, Alessandro | Zamboni, Luca Q.

Article Type: Research Article

Abstract: In this paper we present three new characterizations of Sturmian words based on the lexicographic ordering of their factors.

Keywords: Sturmian words, lexicographic order

DOI: 10.3233/FI-2012-665

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 25-33, 2012

Authors: Castiglione, Giusi | Restivo, Antonio

Article Type: Research Article

Abstract: Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.

Keywords: Regular languages, star-free languages, shuffle of languages, pure submonoids, combinatorics on words

DOI: 10.3233/FI-2012-666

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 35-44, 2012

Authors: Choffrut, Christian

Article Type: Research Article

Abstract: The regular languages in the free monoid generated by a finite alphabet A are exactly the languages that are the models of some sentence of the second-order monadic logic of one successor and a unary predicate for each letter. For trace monoids the natural extension obtained by adapting the successor to the partial order underlying the traces is insufficient to capture the family of their rational subsets. We show that these subsets can be expressed by formulas of the form ∃Γφ where φ is a first-order formula over the structure of traces and Γ is an n-ary predicate semantically restricted, …where n is the cardinality of the alphabet. Show more

Keywords: trace monoid, first-order and second-order logic, rational subsets, finite automata

DOI: 10.3233/FI-2012-667

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 45-50, 2012

Authors: Czeizler, Elena | Mizera, Andrzej | Petre, Ion

Article Type: Research Article

Abstract: To disentangle the numerical contribution of modules to the system-level behavior of a given biomodel, one often considers knock-out mutant models, investigating the change in the model behavior when modules are systematically included and excluded from the model architecture in all possible ways. We propose in this paper a Boolean approach for extracting conclusions about the role of each module from the systematic comparison of the numerical behavior of all knock-out mutants. We associate a Boolean variable to each module, expressing when the module is included in the architecture and when it is not. We can then express the satisfiability …of system-level properties of the full model, such as efficiency, or economical use of resources, in terms of a Boolean formula expressing in a compact way which model architectures, i.e., which combinations of modules, give rise to the desired property. We demonstrate this method on a recently proposed computational model for the heat shock response in eukaryotes. We describe the contribution of each of its three feedback loops towards achieving an economical and effective heat shock response. Show more

Keywords: Model comparison, Boolean approach, feedback loops

DOI: 10.3233/FI-2012-668

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 51-63, 2012

Authors: Diekert, Volker | Kufleitner, Manfred | Steinberg, Benjamin

Article Type: Research Article

Abstract: We give a new proof of the Krohn-Rhodes theorem using local divisors. The proof provides nearly as good a decomposition in terms of size as the holonomy decomposition of Eilenberg, avoids induction on the size of the state set, and works exclusively with monoids with the base case of the induction being that of a group.

Keywords: automaton, decomposition, monoid, transformation monoid, wreath product

DOI: 10.3233/FI-2012-669

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 65-77, 2012

Authors: Gao, Yuan | Yu, Sheng

Article Type: Research Article

Abstract: In this paper, we study the state complexities of four combined operations: L* 1 ∪ L2 , L* 1 ∩ L2 , LR 1 ∪ L2 , and LR 1 ∩ L2 . The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are different from the mathematical compositions of the state complexities of their individual participating operations.

Keywords: state complexity, combined operations, regular languages, finite automata

DOI: 10.3233/FI-2012-670

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 79-92, 2012

Authors: Gogin, Nikita | Hirvensalo, Mika

Article Type: Research Article

Abstract: We give two recursive expressions for both MacWilliams and Chebyshev matrices. The expressions give rise to simple recursive algorithms for constructing the matrices. In order to derive the second recursion for the Chebyshev matrices we find out the Krawtchouk coefficients of the discrete Chebyshev polynomials, a task interesting on its own.

Keywords: Orthogonal polynomials, Krawtchouk polynomials, discrete Chebyshev polynomials, MacWilliams transform, MacWilliams matrices, Chebyshev matrices, Recursion, Krawtchouk coefficients

DOI: 10.3233/FI-2012-671

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 93-110, 2012

Authors: Hage, Jurriaan

Article Type: Research Article

Abstract: Gain graphs are graphs in which each edge has a gain (a label from a group so that reversing the direction of an edge inverts the gain). In this paper we take a generalized view of gain graphs in which the gain of an edge is related to the gain of the reverse edge by an anti-involution, i.e., an anti-automorphism of order at most two. We call these skew gain graphs. Switching is an operation that transforms one skew gain graph into another, driven by a selector that selects an element of some group Γ in each of its vertices. …In this paper, we investigate a generalization of this model, in which we insist that in each vertex v the selected elements are taken from a subgroup Γv of Γ. We call this operation subgroup switching. Our main interest in this paper is in establishing which properties of the theory of switching classes of the skew gain graphs carry over to subgroup switching classes, and which do not. Show more

DOI: 10.3233/FI-2012-672

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 111-122, 2012

Authors: Honkala, Juha

Article Type: Research Article

Abstract: We characterize regular languages as the equality sets of sequences generated by compatible uniform HDT0L systems.

Keywords: Regular language, HDT0L sequence, uniform morphism, equality set

DOI: 10.3233/FI-2012-673

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 123-128, 2012

Authors: Ibarra, Oscar H. | Eğecioğlu, Ömer

Article Type: Research Article

Abstract: A stateless multicounter machine has m-counters operating on a one-way input delimited by left and right end markers. A move of the machine depends only on the symbol under the input head and the sign pattern of the counters. An input string is accepted if, when the input head is started on the left end marker with all counters zero, the machine eventually reaches the configuration where the input head is on the right end marker with all the counters again zero. We bring together a number of results on stateless multicounter automata of various different types: deterministic, nondeterministic, realtime …(the input head moves right at every step), or non-realtime. We investigate realtime and non-realtime machines in both deterministic and nondeterministic cases with respect to the number of counters and reversals. In addition to hierarchy results, we also consider closure properties and the connections to stateless multihead automata. Show more

Keywords: Stateless multicounter machines, reversal-bounded, realtime, non-realtime, hierarchy, stateless multihead automata, closure properties

DOI: 10.3233/FI-2012-674

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 129-140, 2012

Authors: Kari, Jarkko | Le Gloannec, Bastien

Article Type: Research Article

Abstract: The density classification task asks to design a cellular automaton that converges to the uniform configuration that corresponds to the state that is in majority in the initial configuration. We investigate connections of this problem to state-conserving cellular automata. We propose a modified traffic CA that washes out finite islands in the same way as the Gacs, Kurdyumov and Levin automaton, but is also guaranteed to converge to a uniform configuration on rings of odd size. We find experimentally several good classifiers that are close to state-conserving cellular automata, and we observe that the best performing known density classifier by …Wolz and de Oliveira is only a simple swap away from a state-conserving automaton. Show more

Keywords: Cellular automata, density classification, traffic CA

DOI: 10.3233/FI-2012-675

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 141-156, 2012

Authors: Kärki, Tomi

Article Type: Research Article

Abstract: A similarity relation R is a relation on words of equal length induced by a symmetric and reflexive relation on letters. Such a relation is called cyclic if the graph of the relation on letters is a cycle. A chain relation is obtained from a cyclic relation by removing one symmetric relation from the cycle. A word uv is an R-square if u and v are in relation R. The avoidability index of R-squares is the size of the minimal alphabet such that there exists an R-square-free infinite word having infinitely many occurrences of each letter of the alphabet. We …prove that the avoidability index of R-squares is 7 in the case of cyclic relations and 6 in the case of chain relations. We also consider R-overlaps and show that they are 5-avoidable with cyclic relations and 4-avoidable with chain relations. Show more

DOI: 10.3233/FI-2012-676

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 157-174, 2012

Authors: Lacroix, Anne | Rampersad, Narad | Rigo, Michel | Vandomme, Élise

Article Type: Research Article

Abstract: We compute the cardinality of the syntactic monoid of the language 0* repb (m$\mathbb{N}$) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic.

DOI: 10.3233/FI-2012-677

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 175-187, 2012

Authors: Latteux, Michel | Roos, Yves

Article Type: Research Article

Abstract: The family of one-rule grid semi-Thue systems, introduced by Alfons Geser, is the family of one-rule semi-Thue systems such that there exists a letter c that occurs as often in the left-hand side as the right-hand side of the rewriting rule. We prove that for any one-rule grid semi-Thue system S, the set S(w) of all words obtainable from w using repeatedly the rewriting rule of S is a constructible context-free language. We also prove the regularity of the set Loop(S) of all words that start a loop in a one-rule grid semi-Thue systems S.

Keywords: one-rule semi-Thue system, termination, grid semi-Thue system

DOI: 10.3233/FI-2012-678

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 189-204, 2012

Authors: Okhotin, Alexander

Article Type: Research Article

Abstract: The paper investigates the expressive power of language equations with the operations of concatenation and symmetric difference. For equations over every finite alphabet Σ with |Σ| ≥ 1, it is demonstrated that the sets representable by unique solutions of such equations are exactly the recursive sets over Σ, and the sets representable by their least (greatest) solutions are exactly the recursively enumerable sets (their complements, respectively). If |_| ≥ 2, the same characterization holds already for equations using symmetric difference and linear concatenation with regular constants. In both cases, the solution existence problem is Π0 1 -complete, the existence of …a unique, a least or a greatest solution is Π0 2 -complete, while the existence of finitely many solutions is Π0 3 -complete. Show more

DOI: 10.3233/FI-2012-679

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 205-222, 2012

Authors: Rampersad, Narad | Shallit, Jeffrey | Xu, Zhi

Article Type: Research Article

Abstract: In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ* ? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černý, and Restivo's conjecture on the minimal uncompletable word.

Keywords: prefix, suffix, factor, subword, universality, PSPACE-complete, decision problem, polynomial time, synchronizing word, synchronizing automaton, Restivo's conjecture

DOI: 10.3233/FI-2012-680

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 223-236, 2012

Authors: Salomaa, Arto

Article Type: Research Article

Abstract: We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n . The construction leads to cases, where the increase in complexity is maximal in the transition from nondeterministic devices to deterministic ones. We also discuss the crucial importance of the size of the alphabet and present some open problems.

Keywords: state complexity, finite automaton, scheme of automata, nondeterminism, subset construction, mirror image, reversal

DOI: 10.3233/FI-2012-681

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 237-249, 2012

Authors: Séébold, Patrice

Article Type: Research Article

Abstract: We study length-k-overlap-free binary infinite words, i.e., binary infinite words which can contain only overlaps xyxyx with |x| ≤ k − 1. We prove that no such word can be generated by a morphism, except if k = 1. On the other hand, for every k ≥ 2, there exist length-k-overlap-free binary infinite words which are not length-(k − 1)-overlap-free. As an application, we prove that, for every non-negative integer n, there exist infinitely many length-k-overlap-free binary infinite partial words with n holes.

Keywords: Repetition-freeness, length-k-overlaps, partial words, Thue-Morse word, infinite words

DOI: 10.3233/FI-2012-682

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 251-263, 2012

Article Type: Other

Citation: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 265-265, 2012