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}},
}

Webmaster, Wed Sep 16 10:47:00 2009