Finding short readable representation of words I am looking for Input/Literature on


a readable way to represent words (which are accepted by automata)
an Algorithm, that constructs the Representation


For example, a word $w$ might contain a subsequence $v$ which is repeated $m$ times, i.e. $w= u \, \underbrace{v\cdots v}_{100} \,x$ where $u,v,w,x \in \Sigma^*$

In a readable representation, I would expect this subsequence to occur only once, together with the information about the 100 repetitions.



Motivation:

I am working on an interactive input interface for a tool, that works with words that are accepted by automata.
It requires the user to interact with possibly long words 


generated by the system
or select words interactively himself




My Approach:

The representation I currently use structurally can be understood is an ordered tree, where


the leaves are symbols $a \in \Sigma$
the inner nodes are repetition counters $i \in \mathbb{N}$


Example:

$w = ABABAC \, ABABACAC \,ABABACAC \,ABABACAC$

Representations


$\overbrace{AB}^{2}AC\overbrace{\overbrace{AB}^{2}\overbrace{AC}^{2}}^{3}$
$\overbrace{\overbrace{AB}^{2}AC}^{2}\overbrace{AC\overbrace{AB}^{2}AC}^{2}AC$


I have implemented an algorithm which, given $w$, finds the 2. representation.
I would consider 1. more appealing, and I assume, that I would generally prefer representations that are minimal with respect to length (where length is the total amounts of symbols/tree-leaves)



My Questions:


Is there a good algorithm to find representations minimal with respect to length?
Does that have a name? Is there Literature on the topic? (I couldn't find anything useful)
Can someone think of an alternative/better approach?
Given a string $S$ of length $n$, one can find the minimal representation in $O(n^3)$ time using dynamic programming.

Let's consider a representation as a binary tree.  Each node of the tree generates a string (a substring of $S$).  Each leaf generates to a single letter.  The tree has two types of internal nodes: a concatenation node, which generates the concatenation of the strings generated by its two children; and a repetition node, which takes the string generated by its only child and repeats it $r$ times, where $r$ is an integer stored in the node.  Your diagrams can all be represented in this form.

Now given a string $S$, we can find the minimal binary tree that generates it, using dynamic programming.  We'll let $A[i,j]$ denote the minimal binary tree that generates the substring $S[i..j-1]$.

We can derive a recursive expression for $A[i,k]$.  In particular, consider all of the following trees:


a tree with a concatenation node at the root, and a left child $A[i,j]$ and a right child $A[j,k]$ (one such tree for each $j$)
a tree with a repetition node at the root, holding the integer $r$, and a single child $A[i,i+(j-i)/r]$ (one such tree for each divisor $r$ of $j-i$)


We will find the smallest of these trees, and store the result in $A[i,k]$.

By evaluating this recursive relation in a bottom-up fashion (i.e., fill in entries of $A[i,j]$ in order of increasing value of $j-i$), we can fill in the entire table.  There are $O(n^2)$ entries in the table, and each entry takes $O(n)$ time to fill in, so the total running time is $O(n^3)$.



As far as related concepts, your idea is similar to a context-free grammar, augmented with the notion of repetition (e.g., we add a production $A \to r \otimes B$, which means that if a word $w$ that can be produced by $B$, then $w^r$ can be produced by $A$).  I haven't seen that particular notion explored, but context-free grammars are well-explored.

If you want heuristics to find a relatively small representation, but not necessarily the minimal one, you might be interested in the Sequitur algorithm and other uses of context-free grammars for data compression.  I think that the Sequitur algorithm can be modified to work in your setting: i.e., given a string, find a (hopefully small) representation of that string.