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