Search

In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace -complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace -complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL -hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently. A detailed listing of the contributions of this paper can be found at the end of this paper. [ABSTRACT FROM AUTHOR]

Abstract: The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one. We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with , let . Let , let be the number of factors in the prime factorization of n. We give an algorithm to decide whether there exists n, with , and a finite maximal code C which is also factorizing such that . We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in satisfy a property defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set can be embedded in a set satisfying . Furthermore, we prove that, conversely, for each set satisfying , under additional hypotheses, there exists a factorizing code C such that and, as a consequence, is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each , we have , with . In addition, we prove that there exist sets which satisfy and which are not codes. [Copyright &y& Elsevier]

This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based. [Copyright &y& Elsevier]

This paper studies decision problems for semigroups that are word-hyperbolic in the sense of Duncan and Gilman. A fundamental investigation reveals that the natural definition of a ‘word-hyperbolic structure’ has to be strengthened slightly in order to define a unique semigroup up to isomorphism. (This does not alter the class of word-hyperbolic semigroups.) The isomorphism problem is proven to be undecidable for word-hyperbolic semigroups (in contrast to the situation for word-hyperbolic groups). It is proved that it is undecidable whether a word-hyperbolic semigroup is automatic, asynchronously automatic, biautomatic, or asynchronously biautomatic. (These properties do not hold in general for word-hyperbolic semigroups.) It is proved that the uniform word problem for word-hyperbolic semigroups is solvable in polynomial time (improving on the previous exponential-time algorithm). Algorithms are presented for deciding whether a word-hyperbolic semigroup is a monoid, a group, a completely simple semigroup, a Clifford semigroup, or a free semigroup. [ABSTRACT FROM AUTHOR]

Abstract: The paper focuses on deterministic and unambiguous finite automata (DFAʼs and UNFAʼs respectively for short) in the case of a one-letter alphabet. We present a structural characterization of unary UNFAʼs and some considerations relating minimal UNFAʼs with minimum DFAʼs recognizing a given unary language. We also present an algorithm for the construction of a minimal UNFA for a unary regular language. Then we establish a correspondence between pairs of UNFAʼs recognizing a unary language and its complement respectively, and the disjoint covering systems of number theory. It allows us to provide some conditions relating the number of successful simple paths and the lengths of cycles in an UNFA recognizing a unary language with the same parameters in an UNFA recognizing its complement. [Copyright &y& Elsevier]

Abstract: We say that a word w on a totally ordered alphabet avoids the word if there are no subsequences in w order-equivalent to . In this paper we suggest a new approach to the enumeration of words on at most k letters avoiding a given pattern. By studying an automaton which for fixed k generates the words avoiding a given pattern we derive several previously known results for these kind of problems, as well as many new. In particular, we give a simple proof of the formula (Electron. J. Combin. 5(1998) #R15) for exact asymptotics for the number of words on k letters of length n that avoids the pattern . Moreover, we give the first combinatorial proof of the exact formula (Enumeration of words with forbidden patterns, Ph.D. Thesis, University of Pennsylvania, 1998) for the number of words on k letters of length n avoiding a three letter permutation pattern. [Copyright &y& Elsevier]