3
$\begingroup$

let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("Hamming weight") divided by the word length.

what is an algorithm to compute $\max_{x \in L} f(x)$?

there is a simple randomized/ estimation algorithm that computes $f(x)$ over random words; am looking for a deterministic one. note that $f(x)$ evaluated on the shortest word in $L$ is not necessarily the same as the global minimum. am also interested in other generalizations of $f(x)$ that are based on similar "simple word metrics".

bkg: this question arose in studying & idea in attacking an old open number theoretic problem.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Also note that the Parikh image of a regular language is semi-linear; so the set of the pairs $\{ <\#0_w,\#1_w> \mid w \in L\}$ ($\#0_w$ denotes the number of $0$s in $w$) is a union of a finite number of linear sets $\{ c_0 + n_1 c_1 + ... + n_m c_m \mid n_i \in N \}$ where $c_0,...,c_m$ are fixed pairs. $\endgroup$
    – Marzio De Biasi
    Jan 9, 2015 at 17:41
  • $\begingroup$ MDB that sounds like an algorithm will upvote it for 1 if you write it out in more detail & post it thx $\endgroup$
    – vzn
    Jan 9, 2015 at 19:23

2 Answers 2

Reset to default
11
$\begingroup$

First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00 where there is no max. (The sup may not be attained.)

Second, by "FSM" I assume you mean finite automaton.

Then I claim that either the maximum bit density is achieved by a word of length < n, the number of states, or it is given by the maximum bit density over a loop of size at most n. This means there are only finitely many cases to check, for each DFA. Probably with a bit more work, one can get a polynomial-time algorithm out of it.

To see the claim, first note that if we compute the bit density of the sequence of words $(u v^i w)_{i \geq 0}$ then this sequence is either (a) strictly increasing, (b) strictly decreasing, or (c) constant. If the maximum bit density is attained and occurs at a shortest word x of length $>= n$, by the pumping lemma we can write $x = uvw$ where $|uv| \leq n$. In each case we get a contradiction. In (a) there are words with higher bit density, like $uv^2w$; in (b) there is a word with higher bit density, namely $uw$, and in (c) there is a shorter word with the same bit density.

The remaining case is that the maximum density is not attained. A slightly more complicated argument, almost exactly the same as in my paper with Schaeffer, then proves the claim about the loops.

The Critical Exponent is Computable for Automatic Sequences. Luke Schaeffer, Jeffrey Shallit Int. J. Found. Comput. Sci. Vol. 23 No. 8 Pg. 1611-1626
Year: 2012

Improve this answer
$\endgroup$
2
  • $\begingroup$ thx nice insight but dont see it as obviously in P from this sketch (& definitely would prefer an efficient algorithm if possible). it sounds from this like it might be related to looking at all $n$-vertex paths in the FSM graph which could be exponential...? $\endgroup$
    – vzn
    Jan 9, 2015 at 18:59
  • $\begingroup$ I already said the algorithm I suggested wasn't in P. (You didn't specify that in original question.) However, with more work it can probably be done, as in Schaeffer's master's thesis at Waterloo. $\endgroup$
    – Jeffrey Shallit
    Jan 9, 2015 at 21:12
3
$\begingroup$

The supremum bit density will either be achieved by a finite word $v$ in the language, or by the limiting bit density of some sequence $u v w, u v^2 w, u v^3 w, \ldots$ of words in the language, which equals the bit density of $v$. In both cases, we have that $|v| \leq n$ without loss of generality, where $n$ is the number of states in the finite automaton.

Below I give you a polytime algorithm to find $v$. To make the algorithm simpler, I assume the automaton is deterministic. This isn't really essential.

Algorithm: Find $v$.

Let {1,2,...,n} be the set of states.
Let delta be the transition functor.
Let 1 be the initial state.
Let F be the set of accepting states.
Let X be the set of states reachable from the initial state.
Let Y be the set of states that can reach an accepting state.

Let A be an (n+1)-by-(n+1)-by-(n+1) array of strings or NULL.
Set A[i,i,0] = "" for all i in {1,2,...,n}.
Set A[i,j,0] = NULL for all i != j in {1,2,...,n}.
For k in {1,2,...,n} do:
    For i in {1,2,...,n} do:
        For j in {1,2,...,n} do:
            Let W0 = "0" ++ A[delta(i,0), j, k-1]  (or NULL, if A[delta(i,0), j, k-1] is NULL).
            Let W1 = "1" ++ A[delta(i,1), j, k-1]  (or NULL, if A[delta(i,0), j, k-1] is NULL).
            If density(W0) > density(W1) then:     (let density(NULL) = -1 by convention)
                Set A[i,j,k] = W0.
            Else:
                Set A[i,j,k] = W1.

Return highest density non-NULL word
    in     { A[1,j,k] : j in F,              k in {1, ..., n} }
    or in  { A[j,j,k] : j in X intersect Y,  k in {1, ..., n} }.

The idea behind the algorithm is that A[i,j,k] stores the highest density path from state i to state j with length k. We build up this table from k=0 to k=n, and then pick the highest density v that matches our criteria (either it is a word in the language, or it is a loop in some word in the language).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.