Saturday, March 01, 2003

Cardinality Theorem for Regular Languages?

Till Tantau told me an interesting open question at STACS. Kummer proved the following Cardinality Theorem for the recursive sets: Fix a constant k and set A. If there is a recursive function f such that for all x1,...,xk, f(x1,...,xk) is a number between 0 and k that is not |{x1,...,xk}∩A| then A is recursive. The same is not true for polynomial time but is open for regular languages. Details and some partial results in Tantau's paper.

No comments:

Post a Comment