Jakub Kozik

Decidability of density problem for languages

Notion of density is used when there is a need of quantitative
considerations on countable sets. It is known fact that it is
impossible to construct uniformly distributed probabilistic measure
on such set. By now, standard approach to deal with this problem is
to consider asymptotic behavior of probabilities in finite subsets
of elements of bounded size. The well known results of such approach
are 0-1 laws in logic.

In the theory of formal languages notion of density was introduced
by Berstel. First approaches were focused on
regular languages and exploited the theory of formal power series.
Natural extension is the notion of conditional density.

For any language L let l_n denote number of words of length n
in L. Let L,S be languages over finite alphabet such that
S is a subset of L. Let p_n denote probability that randomly and uniformly chosen
word from L of length not greater than n belongs to S.
    Language S  has conditional density in L if and only if there exists the limit
of p_n.

Many problems, concerning asymptotic properties of predicate logic
formulae with bounded number of variables, can be rephrased in the
theory of languages using the above definition.

For the classes of grammars C,D the
        problem of having conditional density is defined as follows:


Given two grammats G_L belonging to C and G_S belonging to D, decide whether
L(G_S) has conditional density in L(G_L).

In my talk I am going to present my result
concerning decidability of the problem of conditional density for
several classes of grammars.