4 papers
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…
Maintaning maximal matching with lookahead
Kitti Gelle, Szabolcs Ivan
In this paper we study the problem of fully dynamic maximal matching with lookahead. In a fully dynamic -vertex graph setting, we have to handle updates (insertions and removals…