Determine the fixpoint of a rewriting system

Feb 12, 2021 • strings • Christoph Dürr
Related problems: [SPOJ:MORPH]

Given the a rewriting system of the form $f:\Sigma\rightarrow \Sigma^\star$ , determine the limit of $f^i(a)$ for some given seed letter $a\in \Sigma$ .

Rewriting system

Consider the infinite sequence $a,f(a),f(f(a)),\ldots$ . In the first step, letter $a$ is replaced by the string $f(a)$ . In the second step every letter in $f(a)$ is replaced by its image by $f$ and the results are concatenated, and so on.

Consider these examples:

$f:\: a \mapsto bb,\: b \mapsto b$: a, bb, bb, bb, …
$f:\: a \mapsto ab,\: b \mapsto a$: a, ab, aba, abaab, abaab, abaababa, abaababaabaab, …
$f:\: a \mapsto ba,\: b \mapsto c,\: c \mapsto b$: a, ba, cba, bcba, cbcba, bcbcba, …

We can observe quite different behaviors. The first example reaches quickly a fixpoint, the second example seems to converge to a fixpoint (in form of an infinite string), but which is not reached within a finite number of steps. And the last example observes some cyclic behavior.

Letter type

This motivates us to distinguish 3 types of letters, depending on properties of the sequence generated by sucessive applications of $f$ starting with the letter $x$ .

Letter $x$ is of type 1 if successive applications of f eventually reach a fixpoint, i.e. if there is an integer i such that $f^i(a)=f^{i+1}(a)$ .
Letter $x$ is of type 2 if for every integer k there is an integer i such that $f^i(x)$ has length at least k and the k first letters are the same in all strings $f^j(x)$ for $j\geq i$ .
Letter $x$ is of type 0 in the remaining case.

Notation

We denote the i-th string in this sequence by $f^i(a)$ . If the sequence has a limit, then denote it by $f^\star(a)$ . In particular if $f^\star(a)$ is a finite string, then it is reached in a finite number of iterations, and $a$ is of type 2. If $f^\star(a)$ is an infinite string, then clearly it is not reached within a finite number of steps, and $a$ is of type 2. (This is less obvious, but I believe it to hold.)

Simplification

We might get rid of letters $x$ which are mapped to the empty string, simply by removing $x$ from all right handsides. This can be done with a queue containing symbols to be removed, and whenever the right hand side of some rule becomes empty, the left hand side enters the queue.

From now on, let’s assume that $f$ does not map to an empty string for all letters considered in the problem.

Rules determining the types

Basic rules:

If $f(x)=x$ , then $x$ has type 1. ( $x$ is a fixpoint for $f$ )
If $f(x)=xw$ for some arbitrary non empty word $w$ , then $x$ is of type 2. Indeed, it generates the sequence $x, xw, xwf(w), xwf(w)f(f(w)), \ldots$ .
If $f(x)=y$ for some letter $y\neq x$ , then clearly $x$ has the same type as $y$ . But if these implications are circular, then $x$ has type 0 (and so have y and all the other letters along the cycle).

More complex rules:

If $f(x) = y_1 y_2 \ldots y_k$ with $y_1 \neq x$ and $k > 1$ , then things become more interesting.

If all letters $y_1 y_2 \ldots y_k$ are of type 1, then so is $x$ . Simply because the limit of f on x is $f^\star(y_1\ldots y_k)$ which is $f^\star(y_1)\ldots f^\star(y_k)$ .

If $y_i$ is the first letter not of type 1, then the type of x is determined by the type of $y_i$ . Again if this leads to a circular dependecy – for example when $y_i=x$ – then $x$ has type 2. Indeed in the limit f will generate on x the string $w^\star$ , where $w$ is the fixpoint reached by $y_1,\ldots,y_{i-1}$ .

How to determine efficiently the types?

We will maintain a table type indexed by the alphabet. Initially all letters have an unknown type, that we could represent by the constant -1. For an implementation in Python, one would like to name the table kind instead to avoid the use of a keyword.

First we apply the basic rules, by setting the type of all letters $x$ with $f(x)=x$ or $f(x)=xw$ .

Then for the remaining letters we inspect a function $g$ , mapping $x$ to the first letter of $f(x)$ . If iterated mapping of $g$ on a letter, ends on a letter with a defined type, then we don’t do anything for the moment. But if it ends on a cycle composed of letters with undefined type, then we know that all letters covered by the cycle need to be set to type 0.

Next, for all letters $x$ of undefined type, we maintain a pointer pos[x] on the string $f(x)$ , such that we already know that all letters before this position have type 1. If the letter pointed by pos[x] has type 1, then clearly we can increment pos[x]. But if it has type is 0 or 2, then the type of $x$ must become the same type (0 or 2). If all letters of $f(x)$ have type 1 (pos[x] exceeds the length of $f(x)$ ), then the type of $x$ is set to $1$ .

And finally we can safely set to 2 the type of all yet undefined letters.

Time complexity

It is $O(kn)$ , where $k$ is the size of the alphabet and $m$ is the total length of the images of $f$ , hence roughly the size of the input.

Implementation in C++

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<vector<int>> f;

bool solve(vector<vector<int>> &f) {
    int n = f.size();
    int kind[n];                // # -1 means undefined, 2 means infinity
    int pos[n] = {0};           
    //  pos[x] is index of first letter of f[x]s with still unknown type
    fill(kind, kind + n, -1);  
    // start with obvious types (kinds)
    for (int x = 0; x < n; x++) {
        if (f[x][0] == x) {
            if (f[x].size() == 1)
                kind[x] = 1;                    // basic type 1 letter
            else
                kind[x] = 2;                    // basic type 2 letter
        }
    }
    // obvious 0 types
    for (int x = 0; x < n; x++) {
        if (kind[x] == -1) {                    // for all yet undefined type letters
            bool seen[n] = {false};             // trace of path
            int y = x;                          // letter walking along path
            while (!seen[y] && kind[y] == -1) { // stop at loop or at defined type letter
                seen[y] = true;
                y = f[y][0];                    // next step in path (restrict f to first letter)
            }                         
            if (seen[y])                        // path ended in a loop
                for (int z = 0; z < n; z++)
                    if (seen[z])
                        kind[z] = 0;            // whole path becomes type 0
        }
    }
    // propage knowledge
    // remaining letters x are of the form 
    // f[x] = y1 y2 ... yk for y1 != x and k>=1
    bool changed = true;
    while (changed) {                               // until fix point reached
        changed = false;        
        // could use priority queue, but for 26 letters trying all is ok
        for (int x = 0; x < n; x++) {
            if (kind[x] == -1) {                    // need to learn type of x
                if (pos[x] == f[x].size()) {        // f maps x only to type 1 letters
                    kind[x] = 1;                    // hence x has type 1 as well
                    changed = true;
                }
                else if (kind[f[x][pos[x]]] == 1) { // additional type 1 letter in prefix
                    pos[x] += 1;
                    changed = true;
                }
                else if (kind[f[x][pos[x]]] != -1) { 
                    kind[x] = kind[f[x][pos[x]]];   // inherit type
                    changed = true;
                }
            }
        }
    }
    // default remaining type is 2
    for (int x = 0; x < n; x++)
        if (kind[x] == -1)
            kind[x] = 2;
    return kind[0] >= 1;    // type of letter 'a'
}

int main(int argc, char const *argv[])
{
    int t, n;
    cin >> t;                   // number of testcases
    while (t-->0) {
        cin >> n;
        vector<vector<int>> f;
        while (n-->0) {         // read mapping f
            string s;
            cin >> s;
            vector<int> image;  
            for (char c: s)     // convert string into int vector
                image.push_back(c - 'a');
            f.push_back(image);
        }
        if (solve(f))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

Comments

Type Comment Here (at least 3 chars)