Fundamenta Informaticae - Volume 116, issue 1-4

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