Published: 3rd September 2023
DOI: 10.4204/EPTCS.386
ISSN: 2075-2180


Proceedings of the 16th International Conference on
Automata and Formal Languages
Eger, Hungary, September 5-7, 2023

Edited by: Zsolt Gazdag, Szabolcs Iván and Gergely Kovásznai

Zsolt Gazdag, Szabolcs Iván and Gergely Kovásznai
Invited Presentation: Operations on Boolean and Alternating Finite Automata
Galina Jirásková
Invited Presentation: Compositions of Weighted Extended Top-Down Tree Transducers
Andreas Maletti
Invited Presentation: On the Degree of Extension of Some Models Defining Non-Regular Languages
Victor Mitrana and Mihaela Păun
A Construction for Variable Dimension Strong Non-Overlapping Matrices
Elena Barcucci, Antonio Bernini, Stefano Bilotta and Renzo Pinzani
Duality of Lattices Associated to Left and Right Quotients
Jason Bell, Daniel Smertnig and Hellis Tamm
Approximate State Reduction of Fuzzy Finite Automata
Miroslav Ćirić, Ivana Micić, Stefan Stanimirović and Linh Anh Nguyen
Weighted Automata over Vector Spaces
Nada Damljanović, Miroslav Ćirić and Jelena Ignjatović
Freezing 1-Tag Systems with States
Szilárd Zsolt Fazekas and Shinnosuke Seki
When Stars Control a Grammar's Work
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi Raman
Comparative Transition System Semantics for Cause-Respecting Reversible Prime Event Structures
Nataliya Gribovskaya and Irina Virbitskaite
On Minimal Pumping Constants for Regular Languages
Markus Holzer and Christian Rauch
Reversible Two-Party Computations
Martin Kutrib and Andreas Malcher
Pumping Lemmata for Recognizable Weighted Languages over Artinian Semirings
Andreas Maletti and Nils Oskar Nuernbergk
State-deterministic Finite Automata with Translucent Letters and Finite Automata with Nondeterministically Translucent Letters
Benedek Nagy
Words-to-Letters Valuations for Language Kleene Algebras with Variable Complements
Yoshiki Nakamura and Ryoma Sin'ya
Solving the Weighted HOM-Problem With the Help of Unambiguity
Andreea-Teodora Nász
Once-Marking and Always-Marking 1-Limited Automata
Giovanni Pighizzini and Luca Prigioniero
A General Approach to Proving Properties of Fibonacci Representations via Automata Theory
Jeffrey Shallit and Sonja Linghui Shan
Separating Words from Every Start State with Horner Automata
Nicholas Tran
Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars
Bianca Truthe
GAPs for Shallow Implementation of Quantum Finite Automata
Mansur Ziiatdinov, Aliya Khadieva and Abuzer Yakaryılmaz


The 16th International Conference on Automata and Formal Languages (AFL 2023) was held in Eger, September 5-7, 2023. It was organized by the Eszterházy Károly Catholic University of Eger, Hungary, and the University of Szeged, Hungary. Topics of interest covered the theory and applications of automata and formal languages and related areas.

The scientific program consisted of invited lectures by

and 18 contributed presentations.

This volume contains the texts of the invited presentations and the 18 papers selected by the International Program Committee from a total of 23 submissions. We would like to thank everybody who submitted a paper to the conference. We are especially grateful to the invited speakers for presenting interesting new developments.

The members of the International Program Committee were

The members of the Steering Committee overseeing the AFL series are

We thank all members of the Program Committee and their subreferees for their excellent cooperation in the selection of the papers. We are grateful to the Faculty of Informatics of the Eszterházy Károly Catholic University of Eger and the Institute of Informatics of University of Szeged for the local organization and financial support of AFL 2023.

Eger, September 2023.

Zsolt Gazdag, Szabolcs Iván, and Gergely Kovásznai

Compositions of Weighted Extended Top-Down Tree Transducers

Andreas Maletti (Universität Leipzig)

Weighted extended top-down tree transducers are a natural generalization of the classic top-down tree transducers, but their compositions pose additional problems due to the extension as well as the weights. We review the basic composition results of [1] of the unweighted case and the basic composition approach of [2] or the weighted case. Additionally we report on recent progress on the conjectures raised in the latter reference. In particular we recently were able to obtain results that mirror the classical composition results for top-down tree transducers.


  1. Joost Engelfriet, Zoltán Fülöp & Andreas Maletti (2017): Composition closure of linear extended top-down tree transducers. Theory of Computing Systems 60(2), pp. 129–171, doi:10.1007/s00224-015-9660-2.
  2. Aurélie Lagoutte & Andreas Maletti (2011): Survey: Weighted Extended Top-Down Tree Transducers Part III – Composition. In: Algebraic Foundations in Computer Science, Lecture Notes in Computer Science 7020, pp. 272–308, doi:10.1007/978-3-642-24897-9_13.