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.

  • 3
    $\begingroup$ Crossposted on CS.SE. $\endgroup$ – Juho May 28 '13 at 22:10
  • 2
    $\begingroup$ For a detailed analysis of one state multicounter machines see Hierarchies and Characterizations of Stateless Multicounter Machines $\endgroup$ – Marzio De Biasi May 30 '13 at 22:15
  • 2
    $\begingroup$ ... and I think that a lot of material/references can be found in recent (>2000) Ibarra's papers $\endgroup$ – Marzio De Biasi May 30 '13 at 22:38
  • 2
    $\begingroup$ Did you ask to Oscar Ibarra? $\endgroup$ – Abuzer Yakaryilmaz May 31 '13 at 4:43
  • 2
    $\begingroup$ @jmite There's no harm in trying :-) As a student myself, I've always gotten a response from a researcher when I've emailed them. In my experience, people are only happy to help out someone who is interested in their research. $\endgroup$ – Juho May 31 '13 at 16:12

Not standard topics, no. And sorry, I have no general overview.

However, I would have a look at the PhD thesis of Klaus Reinhardt for at least a picture of the various families that live in this area. See page 64 for a diagram of the zoo. Motivated by Petri Nets with inhibitor arcs Reinhardt studies priority multicounters with restrictions on when to do zero tests. Non-trivial.

By the way, your last example question was discussed in this forum by user Sam Jones. Another Ibarra reference.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.