ABSTRACT. We study the computational complexity of deciding whether a given deterministic or nondeterministic finite automaton (DFA or NFA) recognizes a language in a given subclass of regular languages. We prove \NL-completeness of this problem on both automata models for the classes of comma-free codes, solid codes, and singleton languages. For the classes of combinational, finitely generated left ideal, star, comet, group, and co-finite languages, the membership problem is \NL-complete on DFAs, and \PSPACE-complete on NFAs. We also show that the membership problem on NFAs is \NL-complete for the classes of prefix-, suffix-, factor-, and subword-free, singletons, and finite languages, and it is \PSPACE-hard for symmetric definite languages. Next, we show that deciding whether a given unary partial DFA recognizes an ordered language is \L-complete, and deciding whether a partial DFA can be ordered is \NP-complete. Finally, deciding whether a given DFA (NFA) recognizes an ordered or power-separating language is \NL-hard (\PSPACE-hard, respectively).

ABSTRACT. For different kinds of reversible finite automata, the complexity of decision problems, such as emptiness, universality, equivalence and inclusion, is investigated. For permutation automata they are all L-complete. For permutation automata with multiple initial states, emptiness is L-complete and the rest are co-NP-complete. For sweeping permutation automata all are co-NP-complete, whereas length-bounded emptiness is PSPACE-complete. For reversible automata, the results are similar to deterministic automata, but universality is easier: L-complete for one initial state (cf. NL-complete for DFA), co-NP-complete for multiple initial states (cf. PSPACE-complete for multiple-entry DFA) and co-NP-complete in the sweeping case (cf. PSPACE-complete for two-way DFA). The minimality problem and the unary case are also investigated.

ABSTRACT. Methods from formal language theory as applied to algebra date back many decades, and give a number of exciting new ways to approach problems in group and semigroup theory. I will give an overview of some of the core questions, their history, their connections with rewriting systems, and some of the (un)decidability results that one can encounter along the way. I will also discuss recent work on undecidability results for subsets defined by monoid automata joint with I. Foniqi and R. D. Gray (East Anglia), as well as recent work with A. Carvalho (NOVA Lisbon) on defining subsets of groups by way of automata and other language-theoretic constructions.

ABSTRACT. We give a practical computer algebra implementation of the Covering Lemma for finite transformation semigroups. The lemma states that given a surjective relational morphism $(X,S)\twoheadrightarrow(Y,T)$, we can establish emulation by a cascade product (subsemigroup of the wreath product): $(X,S)\hookrightarrow (Y,T)\cp (Z,U)$. The dependent component $(Z,U)$ contains the kernel of the morphism, the information lost in the map.

The implementation complements the existing tools for the holonomy decomposition algorithm. It gives an incremental method to get a coarser decomposition when computing the complete skeleton for holonomy is not feasible. Here, we describe a simplified and generalized algorithm for the lemma and compare it to the holonomy method. Incidentally, the kernel-based method could be the easiest way of understanding the hierarchical decompositions of transformation semigroups and thus the celebrated Krohn-Rhodes theory.

ABSTRACT. A language L is said to be C-measurable, where C is a class of languages, if there is an infinite sequence of languages in C that ``converges'' to L. In this paper, we investigate the measuring powers of Gcom of the class of all languages recognised by finite commutative groups and its subclass named MOD. A language is in MOD if membership of a word in the language only depends on its length modulo some fixed integer. In particular, we show that, for a given regular language L, it is decidable whether L is Gcom-measurable (MOD-measurable, respectively) or not. Our results demonstrate that there is a huge gap between the expressive power of group languages and commutative group languages, even from a (very rough) measure theoretic point of view.