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

EPTCS 388

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

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

Preface

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:

Friedrich Otto (Kassel, Germany): A Survey on Automata with Translucent Letters (joint invited lecture with CIAA 2023)
György Vaszil (Debrecen, Hungary): Membrane Computing and Petri Nets

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:

Artiom Alhazov (Institute of Mathematics and Computer Science of Academy of Sciences of Moldova)
Péter Battyányi (University of Debrecen, Hungary)
Martin Berglund (University of Umeå, Sweden)
Erzsébet Csuhaj-Varjú (Eötvös Loránd University, Budapest, Hungary)
Rudolf Freund (TU Wien, Vienna, Austria), co-chair
Zoltán Fülöp (University of Szeged, Hungary)
Géza Horváth (University of Debrecen, Hungary)
Szabolcs Iván (University of Szeged, Hungary)
Sergiu Ivanov (Paris-Saclay University, France)
Miklós Krész (Innorenew, Slovenia and University of Szeged, Hungary)
Zbyněk Křivka (Brno University of Technology, Czech Republic)
Peter Leupold (Germany)
Ian McQuillan (University of Saskatchewan, Canada)
Ludovic Mignot (Université de Rouen Normandie, France)
Nelma Moreira (University of Porto, Portugal)
Benedek Nagy (Eastern Mediterranean University, Famagusta, North Cyprus and Eszterházy Károly Catholic University, Eger, Hungary), co-chair
Beatrice Palano (University of Milan, Italy)
Agustín Riscos-Núñez (Universidad de Sevilla, Spain)
Jose M. Sempere (Universitat Politècnica de València, Spain)
Alexander Szabari (UPJŠ Košice, Slovakia)
Bianca Truthe (University of Giessen, Germany)
György Vaszil (University of Debrecen, Hungary)

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.

References

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.