7 papers · 1 filter
Proceedings of the 16th International Conference on Automata and Formal Languages
Zsolt Gazdag, Szabolcs Iván, Gergely Kovásznai
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 o…
On the number of useful objects in P systems with active membranes
Zsolt Gazdag, Károly Hajagos, Szabolcs Iván
In this paper we investigate the number of objects actually used in the terminating computations of a certain variant of polarizationless P systems with active membranes. The P sys…
On the Order Type of Scattered Context-Free Orderings
Kitti Gelle, Szabolcs Iván
We show that if a context-free grammar generates a language whose lexicographic ordering is well-ordered of type less than , then its order type is effectively computable.
The order type of scattered context-free orderings of rank one is computable
Kitti Gelle, Szabolcs Ivan
A linear ordering is called context-free if it is the lexicographic ordering of some context-free language and is called scattered if it has no dense subordering. Each scattered or…
The ordinal generated by an ordinal grammar is computable
Kitti Gelle, Szabolcs Ivan
A prefix grammar is a context-free grammar whose nonterminals generate prefix-free languages. A prefix grammar is an ordinal grammar if the language is well-ordered with…
Operational characterization of scattered MCFLs -- Technical Report
Zoltan Esik, Szabolcs Ivan
We give a Kleene-type operational characterization of Muller context-free languages (MCFLs) of well-ordered and scattered words.