Publication details

Saarland University Computer Science

Efficiently Computing the Density of Regular Languages

Manuel Bodirsky, Tobias Gärtner, Timo vonOertzen, Jan Schwinghammer

LATIN 2004: Theoretical Informatics: 6th Latin American Symposium, Vol. 2976 of Lecture Notes in Computer Science, pp. 262--270, Springer, 2004

A regular language L is called dense if the fraction fm of words of length m over some fixed signature that are contained in L tends to 1 as m tends to infinity. We present an algorithm that computes the number of accumulation points of (fm) in polynomial time, if the regular language L is given by a finite deterministic automaton, and can then also efficiently check whether L is dense. Deciding whether the least accumulation point of (fm) is greater than a given rational number, however, is coNP-complete. If the regular language is given by a non-deterministic automaton, checking whether L is dense becomes PSPACE-hard. We will formulate these problems as convergence problems of partially observable Markov chains, and reduce them to combinatorial problems for periodic sequences of rational numbers.

Show BibTeX               

Login to edit

Webmaster, Wed Sep 16 10:47:00 2009