2 citations · 3 across the 6 of their papers we have counts for
9 papers
Scattered one-counter languges have rank less than
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…
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…
Reversible Languages Having Finitely Many Reduced Automata
Kitti Gelle, Szabolcs Iván
Reversible forms of computations are often interesting from an energy efficiency point of view. When the computation device in question is an automaton, it is known that the minima…
Recognizing Union-Find trees built up using union-by-rank strategy is NP-complete
Kitti Gelle, Szabolcs Ivan
Disjoint-Set forests, consisting of Union-Find trees, are data structures having a widespread practical application due to their efficiency. Despite them being well-known, no exact…
Recognizing Union-Find trees is NP-complete
Kitti Gelle, Szabolcs Ivan
Disjoint-Set forests, consisting of Union-Find trees are data structures having a widespread practical application due to their efficiency. Despite them being well-known, no exact…
Algebraic Characterization of Forest Logics
Kitti Gelle, Szabolcs Ivan
In this paper we define future-time branching temporal logics evaluated over forests, that is, ordered tuples of ordered, but unranked, finite trees. We associate a rich class FL[$…