# Publication details

##
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

@INPROCEEDINGS{Bodirsky:Gartner:vonOertzen:Schwinghammer:04,
title = {Efficiently Computing the Density of Regular Languages},
author = {Manuel Bodirsky and Tobias G{\"a}rtner and Timo vonOertzen and Jan Schwinghammer},
year = {2004},
editor = {{Martin Farach-Colton}},
publisher = {{Springer}},
booktitle = {LATIN 2004: Theoretical Informatics: 6th Latin American Symposium},
series = {{Lecture Notes in Computer Science}},
volume = {2976},
pages = {{262--270}},
}

Login to edit

Webmaster,
Wed Sep 16 10:47:00 2009