2 citations · 3 across the 6 of their papers we have counts for
6 papers · 1 filter
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…
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…
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[$…