Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Counter machines with two or more counters are typically shown to be equivalent to Turing machines in courses on the theory of computation. However, I have not seen a formal analysis of which languages can be recognized by a one-counter machine. Are these languages equivalent to the context-free languages (perhaps by some clever construction relating them to PDAs), or are they an entirely different class of languages?

share|improve this question
1  
This book: books.google.co.uk/books/about/… by Jean Berstel goes into quite a lot of depth about one-counter languages and other subsets of context-free languages, but, it tends to be very difficult to actually track down a copy of it. –  Sam Jones Dec 24 '12 at 18:17

2 Answers 2

up vote 7 down vote accepted

A one counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). Languages recognized by one counter automata form a proper subset of the context free languages.

For example a 1-counter automata can recognize the language $\{a^nb^n\}$ which is not regular, but cannot recognize the language $\{a^nb^ma^mb^n\}$ which is context free and can be recognized by a 2-counter automata, too.

If k-DCA is a deterministic k-counter automata, and k-NCA is a nondeterministic k-counter automata, then we have the following proper inclusions:

DFA (regular languages) $\subset$ 1-DCA $\subset$ 2-DCA

1-DCA $\subset$ 1-NCA

If we don't allow $\epsilon$ transitions (switch to real time) then k-DCA $\subset$ k'-DCA for k < k'.

Just for completion: there are languages that are context free but cannot be recgnized by counter automatas (k-DCA with k $\geq$ 2) (for example $\{ww^R\}$), and languages recognized by counter automatas that are not context free (for example $\{a^nb^nc^n\}$). A counter automata (in particular a two counter automata) can be Turing complete only if its input and output are properly encoded (see Wikipedia entry for details).

share|improve this answer
    
questions: (1) languages recognized by counter automatas that are not context free you mean not regular? (2) there is a hierarchy for DCA? Why? Aren't they all Turing equivalent (when $k\ge 2$). –  Hendrik Jan Dec 24 '12 at 11:23
    
(1) no I mean "that are not context free" (just pick a properly encoded context sensitive language that can be recognized by a k > 1 counter machine) (2) you are right, the hierarchy refers to real time DCA (I corrected the answer) –  Vor Dec 24 '12 at 14:00

Counter automata were much studied in the ancient formal language past, in the context of AFA and AFL theory (abstract families of automata & languages) by US and French teams (Ginsberg, Greibach, ... , Nivat, Berstel, ...)

Counter automata are typically defined as finite state automata equipped with external memory, consisting of a natural number (or several if you have more than one counter). This number can be incremented, decremented, and (usually) tested for zero. A computation starts with zero and is only accepted when the counter is zero at the end, comparable to the pushdown empty stack acceptance.

If such a machine has at least two such counters then it is equivalent to a Turing machine, even in the deterministic case. The proof of this fact is by Minsky and can be found in the wikipedia article you linked. The model is of course related to the register machine mentioned in the same wikipedia page. The coding-problems mentioned in the wikipedia article are not important in this setting here as we consider automata with an input tape (after all we have to read an input string) whereas wikipedia on this page only assume counters.

This counter automaton can be seen as a special type of pda, having only one stack symbol, and a bottom-of-stack (that is never moved). This enables the automaton to test whether the counter/stack is zero, and act accordingly.

There are in fact three types of counter automata. So combine results wisely or you end up with contradictions (as happened me in the past). All three types are (strictly) included in the context-free languages for one-counter.

The type above stores an integer (or a natural number, that doesn't matter) and can test its contents beiing zero. Blind counter automata store an integer but cannot test for zero. They can expicitly count below zero though. Partially blind counter automata cannot test for zero, but store an natural number. If the machine tries to go below zero it halts without accepting. This is a natural storage type to model Petri nets. It also is ralated to the PDA, now with a single stack symbol without the special bottom marker (and hence the problem of testing for zero: we just get stuck when popping the last stack element). Sometimes the names of the families defined by the respactive counter models are OCL, ROCL and 1-BLIND.

All these families have been studied, they all are (but I am rusty in my AFA/AFL theory) principal full trios (=rational cones) which means they are closed under (inverse) morphisms and intersection with regular languages, and can be obtained using these operations starting with a single language. For the largest family OCL (with zero test) you can start with the language $(Dc)^*$ where $D = \{ w\in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}$ is the "two sided Dyck language on on pair of brackets" (in terminology fitting the subject). There is important intuition related to this language. Symbols $a$ and $b$ reflect popping and pushing, $c$ is the zero test.

As an example of relevant research, Latteux etal have a nontrivial paper "The Family of One-Counter Languages is Closed Under Quotient" (which is actually about ROCL).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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