12
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ Crossposted on CS.SE. $\endgroup$
    – Juho
    May 28, 2013 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, 2013 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, 2013 at 22:38
  • 2
    $\begingroup$ Did you ask to Oscar Ibarra? $\endgroup$
    – Abuzer Yakaryilmaz
    May 31, 2013 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, 2013 at 16:12

1 Answer 1

Reset to default
5
+50
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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