<p>Not standard topics, no. And sorry, I have no general overview.</p>

<p>However, I would have a look at the PhD thesis of <a href="http://www-ti.informatik.uni-tuebingen.de/~reinhard/curr.html#Rei05" rel="nofollow noreferrer">Klaus Reinhardt</a> 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. </p>

<p>By the way, your last example question was discussed in this <a href="https://cs.stackexchange.com/questions/12233/is-the-universe-problem-for-one-counter-automata-with-restricted-alphabet-size-u/">forum</a> by user Sam Jones. Another Ibarra reference.</p>

CC BY-SA 3.0
2013-05-28T21:51:54.703Z
2013-05-28T21:51:54.703Z
2017-04-13T12:48:30.830Z
Hendrik Jan
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>Some example of things I'd look up in this reference:</p>

<ul>
<li>Are all languages accepted by Reversal-bounded Multi-counter machines also accepted by non-reversal-bounded single counter machines?</li>
<li>Are the deterministic reversal-bounded MultiCounter languages closed under left and right concatenation?</li>
<li>Is universality decidable for single-counter machines.</li>
</ul>

<p>These are just example questions, I have many others that come up in my day-to-day work.</p>

<p>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.</p>

CC BY-SA 3.0
2013-05-28T22:10:57.450Z
Crossposted on [CS.SE](http://cs.stackexchange.com/questions/12341/is-there-a-book-survey-paper-outlining-language-class-heiarchies-closure-proper).
Juho
CC BY-SA 3.0
2013-05-30T22:15:18.090Z
For a detailed analysis of one state multicounter machines see [Hierarchies and Characterizations of Stateless
Multicounter Machines](http://www.cs.ucsb.edu/~omer/DOWNLOADABLE/stateless_nonrealtime09.pdfhttp://www.cs.ucsb.edu/~omer/DOWNLOADABLE/stateless_nonrealtime09.pdf)
Marzio De Biasi
CC BY-SA 3.0
2013-05-30T22:38:00.813Z
... and I think that a lot of material/references can be found in recent (>2000) [Ibarra's papers](http://www.cs.ucsb.edu/~ibarra/)
Marzio De Biasi
CC BY-SA 3.0
2013-05-30T22:47:11.803Z
Thanks, that's useful, although it only deals with the stateless case. I'll check out the more recent papers.
Joey Eremondi
CC BY-SA 3.0
2013-05-31T04:43:44.977Z
Did you ask to Oscar Ibarra?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-05-31T06:12:08.513Z
Like, ask him personally? No. If I had a specific question about one of his papers, maybe, but I wouldn't just email him with a reference request.
Joey Eremondi
CC BY-SA 3.0
2013-05-31T16:12:49.120Z
@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.
Juho
CC BY-SA 3.0
2013-05-31T17:10:25.653Z
@jmite, next time please don't cross-post your question. And read the policy about cross-positng linked from our [FAQ]. If you want to move a question to another site ask a moderator.
Kaveh
CC BY-SA 3.0
2013-05-31T17:13:57.527Z
ps: I performed a comment clean up after merging.
Kaveh
CC BY-SA 3.0
2013-06-03T17:19:54.210Z
lance fortnow has recently been talking about ["counting descriptions"](http://blog.computationalcomplexity.org/2013/03/counting-descriptions-new-complexity.html) (nearby? close?) and suggesting that there are lots of open problems in this area. suspect there are links to [timed automata](http://en.wikipedia.org/wiki/Timed_automaton).
vzn
CC BY-SA 3.0
2013-06-05T21:53:26.733Z
I'd really rather not give the bounty to an answer that says "there aren't any sources." So if anybody wants to rephrase their suggestions as an answer you have a good shot at getting a bounty.
Joey Eremondi
CC BY-SA 3.0
2013-06-07T16:21:46.377Z
the question is a bit broad. seems tricky to answer because of two complementary aspects (1) counter machines and (2) "languages above regular and below context free" of which there seem to be many. it seems hard to find papers on the subject of "counting automata" and if fortnow says the field seems to be unmapped, thats an informed opinion. also, maybe some connection to [counter machines](http://en.wikipedia.org/wiki/Counter_machine)?
vzn
<reference-request><co.combinatorics><fl.formal-languages><automata-theory><research-practice>
Is there a book/survey-paper outlining language class hierarchies, closure properties, etc
Joey Eremondi
# Is there a book/survey-paper outlining language class hierarchies, closure properties, etc

(Asked by: username_0 on 2013-05-28)

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.

**Tags:** reference-request, co.combinatorics, fl.formal-languages, automata-theory, research-practice

> **Comments:**
> **username_1**: Crossposted on [CS.SE](http://cs.stackexchange.com/questions/12341/is-there-a-book-survey-paper-outlining-language-class-heiarchies-closure-proper).  
> **username_2**: For a detailed analysis of one state multicounter machines see [Hierarchies and Characterizations of Stateless Multicounter Machines](http://www.cs.ucsb.edu/~omer/DOWNLOADABLE/stateless_nonrealtime09.pdfhttp://www.cs.ucsb.edu/~omer/DOWNLOADABLE/stateless_nonrealtime09.pdf)  
> **username_2**: ... and I think that a lot of material/references can be found in recent (>2000) [Ibarra's papers](http://www.cs.ucsb.edu/~ibarra/)  
> **username_0**: Thanks, that's useful, although it only deals with the stateless case. I'll check out the more recent papers.  
> **username_3**: Did you ask to Oscar Ibarra?  
> **username_0**: Like, ask him personally? No. If I had a specific question about one of his papers, maybe, but I wouldn't just email him with a reference request.  
> **username_1**: @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.  
> **username_4**: @jmite, next time please don't cross-post your question. And read the policy about cross-positng linked from our [FAQ]. If you want to move a question to another site ask a moderator.  
> **username_4**: ps: I performed a comment clean up after merging.  
> **username_5**: lance fortnow has recently been talking about ["counting descriptions"](http://blog.computationalcomplexity.org/2013/03/counting-descriptions-new-complexity.html) (nearby? close?) and suggesting that there are lots of open problems in this area. suspect there are links to [timed automata](http://en.wikipedia.org/wiki/Timed_automaton).  
> **username_0**: I'd really rather not give the bounty to an answer that says "there aren't any sources." So if anybody wants to rephrase their suggestions as an answer you have a good shot at getting a bounty.  
> **username_5**: the question is a bit broad. seems tricky to answer because of two complementary aspects (1) counter machines and (2) "languages above regular and below context free" of which there seem to be many. it seems hard to find papers on the subject of "counting automata" and if fortnow says the field seems to be unmapped, thats an informed opinion. also, maybe some connection to [counter machines](http://en.wikipedia.org/wiki/Counter_machine)?  

---

## 1 answers

### Answer by username_6 on 2013-05-28. Score: 5 | Accepted answer

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

However, I would have a look at the PhD thesis of [Klaus Reinhardt](http://www-ti.informatik.uni-tuebingen.de/~reinhard/curr.html#Rei05) 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](https://cs.stackexchange.com/questions/12233/is-the-universe-problem-for-one-counter-automata-with-restricted-alphabet-size-u/) by user Sam Jones. Another Ibarra reference.


---

