Published: 15th September 2023|
|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|
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:
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
In this talk (see also the survey paper in the co-located CIAA proceedings: ), 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.
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.