CS Paper Radar

Proceedings 17th International Conference on Automata and Formal Languages

Michal Hospodár, Galina Jirásková, Viktor Olejár, Juraj Šebej, György Vaszil

cs.FL cs.CC ·submitted 2026-08-24 10:17 UTC · v1
publishedhot direction

Abstract

The 17th International Conference on Automata and Formal Languages (AFL 2026) was held in Košice, September 7-10, 2026. It was organized by the Faculty of Science, P. J. Šafárik University in Košice and the Mathematical Institute of the Slovak Academy of Sciences. This volume contains the texts of the three invited lectures and the 18 papers selected by the Program Committee from a total of 27 submissions. The accepted papers, submitted by authors from 14 countries, cover all important areas of automata and formal language theory and their applications such as grammars and acceptors for strings, trees, and graphs, algebraic theories and algorithms for automata and languages, decision problems, relations to complexity theory, picture description and analysis, and other fields.

Journal ref
EPTCS 451, 2026
DOI
10.4204/EPTCS.451

Closest papers

Nearest neighbours by meaning across the whole index.

Shortest Synchronizing Words on Product Automata

cs.FL ·2026-11-06 ·Henning Fernau, Igor Rystsov
similarity 0.67
Abstract

We consider some operations on finite automata graphs, in particular various product, union and merge operations, and investigate how they relate to the parameter~$\mathrm{rt}$, the \emph{length of a shortest synchronizing word}. We derive some lower and upper bounds for the operations that we study. We also examine several classes of automata (for instance, partially ordered, commutative or idempotent automata) that are preserved under these operations and show in which way the parameter $\mathrm{rt}$ behaves in these automata classes. Also, we consider automata classes that can be constructed by combining automata from better known classes; in particular, these new classes of automata will also satisfy the bound of the famous Černý conjecture. This also motivates us to study even more closure properties. In particular, we show that certain automata classes related to synchronization form pseudo-varieties. We also commence a similar study concerning the length of shortest homing sequences of Mealy automata.

0.13

Proceedings Seventeenth International Symposium on Games, Automata, Logics, and Formal Verification

cs.LO cs.FL ·2026-10-06 ·Giorgio Bacci, Mickaël Randour
published similarity 0.65
Abstract

This volume contains the proceedings of GandALF 2026, the Seventeenth International Symposium on Games, Automata, Logics, and Formal Verification. The symposium was held in Aalborg, Denmark, on September 15-17, 2026. The aim of GandALF 2026 is to bring together researchers from academia and industry who are actively working in the fields of Games, Automata, Logics, and Formal Verification. The idea is to cover an ample spectrum of themes, ranging from theory to applications, and stimulate cross-fertilisation.

0.33

Graph-based automata

cs.FL math.CO ·2026-09-08 ·Cyril Pujol
theory similarity 0.64
Abstract

We study graph-based automata: nondeterministic finite automata obtained from edge-colored or oriented graphs by taking every vertex as both initial and accepting, and every edge as a pair of opposite transitions. The language of these automata corresponds to the set of edge-colored or oriented paths mapping to their corresponding graphs. We develop an analogous notion for trees and characterise the languages recognised by these models. For tree languages we prove the existence of a unique size- minimal graph and, more generally, a homomorphism-minimal graph for both word and tree languages using duality methods. In order to further motivate these models, we showcase a few results at the inter- section between graph theory and automata theory: We relate graph-based automata to reversible automata, give a decomposition of graph-based languages into reversible languages, and introduce the remanent language of an undirected graph as the inter- section of all its orientations. This remanent language captures structural information on the graph such as chromatic number.

0.19

Every Regular Language Has a Bipartite Cactus Automaton

cs.FL ·2026-10-08 ·Mario Grobler, Till Koziel, Sebastian Siebertz
published similarity 0.64
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Thompson's classical construction turns every regular expression into an equivalent epsilon-NFA whose transition graph is series-parallel. The construction uses epsilon-transitions, and eliminating them by the usual shortcut construction need not preserve planarity or the bound of two on the treewidth of the transition graph. Book and Chandra proved that every regular language nevertheless has an epsilon-free NFA with a planar transition graph. We show that the transition graph can in fact be chosen to be a bipartite cactus: every cycle is even, and any two cycles have at most one vertex in common. In particular, it is outerplanar and has treewidth at most two. This is a considerably more simple structure than the general series-parallel guarantee supplied by Thompson's construction. The proof is a direct induction on parity-typed regular expressions and uses only elementary closure properties of cactus graphs.

0.32

Inductive Inference of Cellular Automata

cs.FL ·2026-08-25 ·Martin Kutrib, Ian McQuillan, Priscilla Raucci, Matthias Wendlandt
publishedhot direction similarity 0.62
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Inductive inference of one- and two-way cellular automata (CA) is considered. This involves inferring a CA that is compatible with a finite amount of available data. In this paper, this information is provided in the form of a finite set of intervals, where each interval consists of two words w and w' over a state set alphabet, with a positive integer i. The goal is to infer a CA which is compatible with each interval (w,w',i), meaning that it can derive w' from w in i steps. We consider three variations of this problem, 1) where the CA is completely known a priori, and the goal is therefore to verify compatibility, 2) where the CA is partially known a priori and the goal is to extend it to a full CA that is compatible, and 3) where the CA is completely unknown, and the goal is to fully construct one that is compatible if one exists. With all three variations, inference can be completed in polynomial time, and is in fact P-complete.

0.46

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown automaton, we first consider, for each string in its language, the minimum number of turns made in accepting computations (weak measure). We prove that it is decidable whether a pushdown automaton accepts a bounded language in a constant number of turns and whether it accepts a bounded language in k turns, for any given k>=0. This is in contrast to the general case, in which these problems are known to be undecidable, with the exception of acceptance in 0 turns, which is decidable. Furthermore, we prove that when the number of turns sufficient to accept a bounded language is not limited by any constants, it linearly grows with respect to the input length. Also this is in contrast with the general case where, for each nonnegative k, there exists a language for which the number of turns necessary and sufficient is of the order of log^(k), the k times composition of the logarithm with itself. We also prove that, when the costs of all accepting computations are taken into account (accept measure), a linear lower bound for the number of turns, if not limited by any constants, holds even removing the restriction to bounded languages.

0.43

Weighted Alternating Tree Automata

cs.FL ·2026-08-25 ·Olle Torstensson
published similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We define weighted alternating tree automata — a generalization of weighted (non-alternating) tree automata, (unweighted) alternating tree automata, and weighted alternating (string) automata — over commutative semirings. We study their expressive power, and show that it is equivalent to that of weighted tree automata exactly when the employed semiring is locally finite. In our main result, we characterize the class of weighted tree languages defined by weighted alternating tree automata as the closure of the recognizable weighted tree languages under inverse tree homomorphisms.

0.46

Synchronizing Automata: Open Problems

cs.FL ·2026-08-25 ·Marek Szykuła
publishedsurveyhot directionhighly cited similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We survey selected open problems in the theory of synchronizing automata, centered around the famous Černý conjecture. A deterministic finite automaton is called synchronizing if it admits a reset word whose action maps all states to a single state. The Černý conjecture states that every synchronizing automaton with n states possesses a reset word of length at most (n-1)^2. We discuss avoiding words, compressing a state with another, synchronization of a (given or any) subset, complexity of deciding the synchronizability, average reset threshold, and linear-algebraic methods. Some new auxiliary results are also presented.

0.72