Papers for

formal language tool developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Classification of prime deterministic automata over finite alphabets

Prime Accessible Deterministic Automata

Abstract: We classify prime accessible deterministic automata over finite alphabets, both among finite automata and among automata with arbitrary state sets. Every one-state automaton is prime. Over a one-letter alphabet, a finite nontrivial automaton is prime exactly when it is a cycle of prime-power length or a finite chain ending in a fixed state. The unique infinite accessible unary automaton, up to isomorphism, is also prime. Every nontrivial automaton over an alphabet with at least two letters is not prime. Shen proved the finite case; we give a shorter proof. We also characterize a decomposition of the automaton whose states are all finite input words. The reachable product of the quotients by the least right congruences identifying the empty word with nonempty words $p$ and $q$, respectively, is isomorphic to this automaton exactly when $p^r\ne q^s$ for all positive integers $r,s$.

Fri 9 OctFormal Languages and Automata Theory
The gist
This paper identifies which simple types of deterministic state machines, called automata, are 'prime'—meaning they cannot be broken down further. The authors show that all single-state machines are prime and that over a single-letter alphabet, prime automata correspond to cycles with lengths based on prime powers or simple chains. They confirm that more complicated machines with two or more letters are not prime. They also analyze the structure of infinite automata built from all finite input words and offer a precise condition when certain combinations of these automata are isomorphic.
Open → 2610.13274v1

New automaton model characterizes complex graph encodings efficiently

Recognizers for Graph-Encoding Languages

Abstract: We introduce recurrent incidence automata (RIAs), a new automaton model motivated by a decomposition of certain two-stack visibly pushdown computations. The decomposition separates vertex-local finite-state computations from recurrent one-stack interfaces connecting consecutive vertices. The construction is motivated by a two-stack visibly pushdown encoding of arbitrary ordered graphs whose strings admit a unique factorization into center-foldable vertex-local factors and whose auxiliary stack is empty at every factor boundary. Folding each factor into a sequence of pair symbols yields a local interface transformation. An RIA consists of a finite-state unit that computes these transformations and a recurrent layer that composes them across consecutive factors. Rather than manipulating an internal pushdown store, RIAs externalize long-range stack memory into recurrent interfaces between local computations. We show that nondeterministic RIA languages are closed under union, intersection, concatenation, Kleene-*, and reversal. Deterministic RIAs are closed under Boolean operations, although emptiness remains undecidable.

Mon 5 OctFormal Languages and Automata TheoryComputational ComplexityDiscrete Mathematics
The gist
Understanding complex graph structures can be challenging when using traditional string-based methods. The authors introduce recurrent incidence automata (RIAs), a new way to process graph-encoded strings by breaking them down into simpler vertex-based parts connected through recurring patterns. Instead of handling complicated long-term memory internally, their model manages connections between parts externally using a special recurrent layer. This approach allows recognizing certain languages of graphs with useful closure properties, though some questions like emptiness remain computationally hard.
Open → 2610.06743v1

Limits and conditions for learning word patterns with queries

Learning Shuffle Ideals with Membership Queries and Contrastive Examples

Abstract: This paper studies learning of shuffle ideals with membership queries as well as with contrastive queries---a form of membership query that reveals not only whether a selected word $w$ is in the target language or not, but also provides a most similar word $w'$ that belongs to the target language if %and only if $w$ does not. For both settings, it is shown that even some very simple classes of shuffle ideals cannot be learned efficiently. By contrast, we obtain positive learnability results for classes of shuffle ideals that meet certain structural conditions. In the case of membership queries, these structural conditions are related to the previously studied notion of universal words, and raise new questions in word combinatorics. In the case of contrastive queries, the structural conditions relate to partitioning sets of words that are listed in shortlex order.

Sat 26 SeptFormal Languages and Automata TheoryMachine Learning
The gist
This paper investigates how to learn special sets of words, called shuffle ideals, by asking questions about whether words belong to them. It shows that for simple types of these word sets, learning them efficiently is impossible, even if the questions provide helpful contrast examples. However, the authors identify specific structural features that make some classes of shuffle ideals learnable. These features relate to how words are universally ordered or grouped, raising new research questions about word patterns.
Open → 2609.32820v1