Search

Journal of Automata, Languages and Combinatorics, Volume 27, Numbers 1-3, 2022, 3-13

Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack content during runs of the pushdown automaton, is first constructed in a forward procedure to determine which transitions are reachable, and then employed in a backward procedure to determine which of these transitions can lead to a final state. An implementation of the algorithm is shown to exhibit a favorable performance.

In this paper, we continue the research on networks of evolutionary processors where the filters belong to several special families of regular languages. These subregular families are defined by restricting the resources needed for generating or accepting them (the number of states of the minimal deterministic finite automaton accepting a language of the family as well as the number of non-terminal symbols or the number of production rules of a right-linear grammar generating such a language). We insert the newly defined language families into the hierachy of language families obtained by using as filters languages of other subregular families (such as languages which are ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, combinational, finite, monoidal, nilpotent, commutative, codes, or ideals)., Journal of Automata, Languages and Combinatorics, Volume 25, Numbers 2-3, 2020, 83-113

It was conjectured by Černý in 1964 that a synchronizing DFA on n states always has a shortest synchronizing word of length at most (n−1) 2 (n−1)2, and he gave a sequence of DFAs for which this bound is reached. In 2006 Trahtman conjectured that apart from Černý’s sequence only 8 DFAs exist attaining the bound. He gave an investigation of all DFAs up to certain size for which the bound is reached, and which do not contain other synchronizing DFAs. Here we extend this analysis in two ways: we drop this latter condition, and we drop limits on alphabet size. For n≤4 n≤4 we do the full analysis yielding 19 new DFAs with smallest synchronizing word length (n−1) 2 (n−1)2, refuting Trahtman’s conjecture. All these new DFAs are extensions of DFAs that were known before. For n≥5 n≥5 we prove that none of the DFAs in Trahtman’s analysis can be extended similarly. In particular, as a main result we prove that the Černý examples C n Cn do not admit non-trivial extensions keeping the same smallest synchronizing word length (n−1) 2 (n−1)2.

In the area of formal languages and automata theory, regular languages and finite automata are widely studied. Several classes of specific finite automata and their accepted languages have been investigated, for example, definite automata and non-counting automata. Subfamilies of the family of the regular languages can also be motivated by their specific representations as regular expressions, for example, the family of the union-free languages or the family of the star-free languages. Another line of research is to consider subfamilies of the family of the regular languages which are based on ressources needed for generating or accepting them (like the number of non-terminal symbols, production rules, or states). In this paper, we prove inclusion relations and incomparabilities of subregular language families which are based on structural properties (like the set of all suffix-closed or commutative regular languages) or on descriptional complexity measures.

We present a minimization algorithm for finite state automata that finds and merges bisimulation-equivalent states, identified through partition aggregation. We show the algorithm to be correct and run in time \( O \left( n^2 d^2 \left| \Sigma \right| \right) \), where n is the number of states of the input automaton \(M\), d is the maximal outdegree in the transition graph for any combination of state and input symbol, and \(\left| \Sigma \right| \) is the size of the input alphabet. The algorithm is slower than those based on partition refinement, but has the advantage that intermediate solutions are also language equivalent to \(M\). As a result, the algorithm can be interrupted or put on hold as needed, and the derived automaton is still useful. Furthermore, the algorithm essentially searches for the maximal model of a characteristic formula for \(M\), so many of the optimisation techniques used to gain efficiency in SAT solvers are likely to apply.