I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack counter machines, deterministic CFLs, etc.
I'm wondering if anybody knows of a good book or survey paper which outlines the properties of these languages. Most of what I'm looking at is too obscure or too new to be in my Hopcroft-Ullman book, even the 1979 edition.
Mainly I'm looking for which language classes are contained in one-another, the closure properties of these languages, and the decidability of basic problems (F-problems) on these languages.
Some example of things I'd look up in this reference:
- Are all languages accepted by Reversal-bounded Multi-counter machines also accepted by non-reversal-bounded single counter machines?
- Are the deterministic reversal-bounded MultiCounter languages closed under left and right concatenation?
- Is universality decidable for single-counter machines.
These are just example questions, I have many others that come up in my day-to-day work.
As a starting point, I've tried tracing which papers cite Oscar Ibarra's "Reversal-Bounded Multicounter Machines and Their Decision Problems", but haven't found much.