12
$\begingroup$

What is the simplest computational model for which the emptiness problem is undecidable?

Emptiness problem for a computational model (e.g. finite state automaton, alternating pushdown automaton, bounded-error quantum automaton with a counter, deterministic LBA, etc.) is to determined whether, for a given such machine, the language recognized/defined by this machine is empty. Here the description of the machine should be finite!

I know that the word "simplest" is a little vague. There could be more than one answer for some incomparable computational models.

As a special remark, I believe that the question would become more interesting by focusing on unary and binary alphabets separately.

Note that there are many computational models for which the halting problem is decidable but the emptiness problem (and some other problems) is (are) undecidable, e.g. Linear bounded automata (LBAs).

Improve this question
$\endgroup$
3
  • $\begingroup$ dont follow the question but the simplest model is likely to be trivial or toylike. did you mean exactly the opposite, the least simple? FSMs are often regarded as one of the simplest computational models... $\endgroup$
    – vzn
    Commented Mar 25, 2014 at 4:50
  • $\begingroup$ Is there a reason to believe that halting and emptiness should be related ? $\endgroup$
    – babou
    Commented Mar 25, 2014 at 17:37
  • $\begingroup$ @babou: No! I just tried to point that decidability of emptiness problem is interesting for restricted models, but that of halting problem, the most well-known one among others, is not. $\endgroup$
    – Abuzer Yakaryilmaz
    Commented Mar 25, 2014 at 19:12

1 Answer 1

Reset to default
15
$\begingroup$

Probably you already got these in your bag :-)

  • Two way one counter machine over unary alphabet (Minsky61).
  • Two way weak counter machines (the counter has no effect on the computation but the machine halts if counter reaches zero) [1].
  • Quantum one counter automata [2].

With binary alphabets, the emptiness remains undecidable for:

  • One way machines with one unbounded counter and one pushdown store that makes at most one reversal [3].

  • Two-way machines deterministic finite automata with multiple reversal bounded counters (even over a bounded language) [3].

  • Stateless (the transitions depend only on the scanned symbol) 2-head 2-way deterministic finite automata even when each head makes only one reversal on the input tape [4].

Edit: on the boundary:

  • (Open problem) Is the emptiness problem decidable for two-way nondeterministic finite automata with one reversal bounded counter over non-bounded languages? (over bounded languages it is decidable [5])

[1] Tat-hung Chan. On Two-Way Weak Counter Machines. Mathematical Systems Theory 01/1987;
[2] Richard F. Bonner, Rusins Freivalds, and Maksim Kravtsev. 2001. Quantum versus Probabilistic One-Way Finite Automata with Counter. In Proceedings of the 28th Conference on Current Trends in Theory and Practice of Informatics Piestany: Theory and Practice of Informatics (SOFSEM '01), Leszek Pacholski and Peter Ruzicka (Eds.). Springer-Verlag, London, UK, UK, 181-190.
[3] Oscar H. Ibarra. 1978. Reversal-Bounded Multicounter Machines and Their Decision Problems. J. ACM 25, 1 (January 1978), 116-133.
[4] Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin, On stateless multihead automata: Hierarchies and the emptiness problem, Theoretical Computer Science, Volume 411, Issue 3, 6 January 2010, Pages 581-593, ISSN 0304-3975.
[5] Zhe Dang, Oscar H. Ibarra, Zhi-wei Sun. On the emptiness problems for two-way nfa with one reversal-bounded counter. In Proc. Thirteenth Int. Symp. on Algorithms and Computation (2002)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wow ... Is there a site with all that information nicely organized regarding decisions on automata and languages? Same question for closure properties. $\endgroup$
    – babou
    Commented Mar 25, 2014 at 17:06
  • 3
    $\begingroup$ @babou: I don't know, but I agree with you, an "Automata Zoo" or a site like graphclasses.org would be very useful (and I also noticed that it's probably the right time for a survey paper on the subject). $\endgroup$
    – Marzio De Biasi
    Commented Mar 25, 2014 at 17:14

Your Answer

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

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