Published: 15th September 2023
DOI: 10.4204/EPTCS.388
ISSN: 2075-2180


Proceedings of the 13th International Workshop on
Non-Classical Models of Automata and Applications
Famagusta, North Cyprus, 18th-19th September, 2023

Edited by: Benedek Nagy and Rudolf Freund

Rudolf Freund and Benedek Nagy
Invited Presentation: A Survey on Automata with Translucent Letters
Friedrich Otto
Invited Presentation: Membrane Computing and Petri Nets
György Vaszil
Generating Semantic Graph Corpora with Graph Expansion Grammar
Eric Andersson, Johanna Björklund, Frank Drewes and Anna Jonsson
Formalizing BPE Tokenization
Martin Berglund and Brink van der Merwe
On Languages Generated by Signed Grammars
Ömer Eğecioğlu and Benedek Nagy
Final Sentential Forms
Tomáš Kožár, Zbyněk Křivka and Alexander Meduna
Deterministic Real-Time Tree-Walking-Storage Automata
Martin Kutrib and Uwe Meyer
Latvian Quantum Finite State Automata for Unary Languages
Carlo Mereghetti, Beatrice Palano and Priscilla Raucci
Constituency Parsing as an Instance of the M-monoid Parsing Problem
Richard Mörbitz
Forgetting 1-Limited Automata
Giovanni Pighizzini and Luca Prigioniero
Sweeping Permutation Automata
Maria Radionova and Alexander Okhotin
Merging two Hierarchies of Internal Contextual Grammars with Subregular Selection
Bianca Truthe
Ordered Context-Free Grammars Revisited
Brink van der Merwe


The Thirteenth International Workshop on Non-Classical Models of Automata and Applications (NCMA 2023) was held in Famagusta, North Cyprus, on September 18 and 19, 2023, organized by the Eastern Mediterranean University. The NCMA workshop series was established in 2009 as an annual event for researchers working on non-classical and classical models of automata, grammars or related devices. Such models are investigated both as theoretical models and as formal models for applications from various points of view. The goal of the NCMA workshop series is to exchange and develop novel ideas in order to gain deeper and interdisciplinary coverage of this particular area that may foster new insights and substantial progress.

The previous NCMA workshops took place in the following places: Wrocław, Poland (2009), Jena, Germany (2010), Milano, Italy (2011), Fribourg, Switzerland (2012), Umeå, Sweden (2013), Kassel, Germany (2014), Porto, Portugal (2015), Debrecen, Hungary (2016), Prague, Czech Republic (2017), Košice, Slovakia (2018), Valencia, Spain (2019). Due to the Covid-19 pandemic there was no NCMA workshop in 2020 and 2021. The Twelfth International Workshop on Non-Classical Models of Automata and Applications (NCMA 2022) was organized by the Faculty of Informatics of the University of Debrecen, Hungary. NCMA 2023, organized by the Eastern Mediterranean University, in Famagusta, North Cyprus, was co-located with the 27th International Conference on Implementation and Application of Automata (CIAA 2023, 19-22 September).

The invited lectures at NCMA 2023 have been the following:

The 11 regular contributions have been selected out of 15 submissions by a total of 29 authors from 10 different countries by the following members of the Program Committee:

In addition to the invited lectures and the regular submissions, NCMA 2023 also featured three short presentations to emphasize the workshop character. This volume contains the invited and regular presentations.

A special issue of the journal Acta Informatica containing extended versions of selected regular contributions to NCMA 2023 will also be edited after the workshop. The extended papers will undergo the standard refereeing process of the journal.

We are grateful to the two invited speakers, to all authors who submitted a paper to NCMA 2023, to all members of the Program Committee, their colleagues who helped evaluating the submissions, and to the members of the Eastern Mediterranean University who were involved in the local organization of NCMA 2023.

30th of August, 2023 Rudolf Freund
Benedek Nagy

A Survey on Automata with Translucent Letters

Friedrich Otto (Universität Kassel)

In this talk (see also the survey paper in the co-located CIAA proceedings: [1]), we present the various types of automata with translucent letters that have been studied in the literature. These include the finite automata and the pushdown automata with translucent letters, which are obtained as reinterpretations of certain cooperating distributed systems of a restricted type of restarting automaton, the linear automaton with translucent letters, and the visibly pushdown automaton with translucent letters. For each of these types of automata with translucent letters, it has been shown that they accept those trace languages which are obtained from the class of languages that is accepted by the corresponding type of automaton without translucent letters.


  1. Friedrich Otto (2023): A Survey on Automata with Translucent Letters. In Benedek Nagy, editor: Proceedings of the 27th International Conference on Implementation and Application of Automata, CIAA 2023, Famagusta, North Cyprus, September 19–22, 2023, Lecture Notes in Computer Science 14151, Springer, pp. 21–50, doi:10.1007/978-3-031-40247-0_2.

Membrane Computing and Petri Nets

György Vaszil (University of Debrecen)

When looking at the computations of membrane systems and the behavior of place/transition Petri nets, we might notice several features which are related to each other. Petri net transitions consume tokens from their input places and produce new tokens at their output places, so in some sense they behave similarly to membrane systems which consume, produce, and move objects around in the regions of their membrane structure. Based on these relationships, the functioning of place/transition nets can naturally be described by transformations of multisets corresponding to possible token distributions on the places of the net, while different kinds of objects and object evolution rules in different compartments of a membrane system can be represented by the places and transitions of a Petri net.

In the talk we look in more detail at these structural links between the two models which, on one hand, motivate the examination of membrane systems from the point of view of the concurrent nature of their behavior, and on the other hand, inspires the study of Petri net variants suitable for the modeling of membrane system computations.