Formal Languages and Automata Theory (cs.FL)

  • PDF
    Automata learning has been successfully applied in the verification of hardware and software. The size of the automaton model learned is a bottleneck for scalability and hence optimizations that enable learning of compact representations are important. In this paper, we continue the development of a general framework for automata learning based on category theory and develop a class of optimizations and an accompanying correctness proof for learning algorithms. The new algorithm is parametric on a monad, which provides a rich algebraic structure to capture non-determinism and other side-effects. These side-effects are used to learn more compact automaton models and the abstract categorical approach enables us to capture several possible optimizations under the same (p)roof.
  • PDF
    A word $w$ is \emphextending a subset of states $S$ of a deterministic finite automaton, if the set of states mapped to $S$ by $w$ (the preimage of $S$ under the action of $w$) is larger than $S$. This notion together with its variations has particular importance in the field of synchronizing automata, where a number of methods and algorithms rely on finding (short) extending words. In this paper we study the complexity of several variants of extending word problems: deciding whether there exists an extending word, an extending word that extends to the whole set of states, a word avoiding a state, and a word that either extends or shrinks the subset. Additionally, we study the complexity of these problems when an upper bound on the length of the word is also given, and we consider the subclasses of strongly connected, synchronizing, binary, and unary automata. We show either hardness or polynomial algorithms for the considered variants.
  • PDF
    An automaton is partially ordered if the only cycles in its transition diagram are self-loops. The expressivity of partially ordered NFAs (poNFAs) can be characterized by the Straubing-Thérien hierarchy. Level 3/2 is recognized by poNFAs, level 1 by confluent, self-loop deterministic poNFAs as well as by confluent poDFAs, and level 1/2 by saturated poNFAs. We study the universality problem for confluent, self-loop deterministic poNFAs. It asks whether an automaton accepts all words over its alphabet. Universality for both NFAs and poNFAs is a PSpace-complete problem. For confluent, self-loop deterministic poNFAs, the complexity drops to coNP-complete if the alphabet is fixed but is open if the alphabet may grow. We solve this problem by showing that it is PSpace-complete if the alphabet may grow polynomially. Consequently, our result provides a lower-bound complexity for some other problems, including inclusion, equivalence, and $k$-piecewise testability. Since universality for saturated poNFAs is easy, confluent, self-loop deterministic poNFAs are the simplest and natural kind of NFAs characterizing a well-known class of languages, for which deciding universality is as difficult as for general NFAs.
  • PDF
    Piecewise testable languages form the first level of the Straubing-Thérien hierarchy. The membership problem for this level is decidable and testing if the language of a DFA is piecewise testable is NL-complete. The question has not yet been addressed for NFAs. We fill in this gap by showing that it is PSpace-complete. The main result is then the lower-bound complexity of separability of regular languages by piecewise testable languages. Two regular languages are separable by a piecewise testable language if the piecewise testable language includes one of them and is disjoint from the other. For languages represented by NFAs, separability by piecewise testable languages is known to be decidable in PTime. We show that it is PTime-hard and that it remains PTime-hard even for minimal DFAs.