1
$\begingroup$

I am looking for Input/Literature on

  1. a readable way to represent words (which are accepted by automata)
  2. 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

  1. $\overbrace{AB}^{2}AC\overbrace{\overbrace{AB}^{2}\overbrace{AC}^{2}}^{3}$
  2. $\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:

  1. Is there a good algorithm to find representations minimal with respect to length?
  2. Does that have a name? Is there Literature on the topic? (I couldn't find anything useful)
  3. Can someone think of an alternative/better approach?
$\endgroup$
  • 2
    $\begingroup$ You seem do have re-invented a subset of (extended) regular expressions. What you have in 1. what commonly be written as $(AB)^2AC ((AB)^2(AC)^2)^3$. You can add spaces for readibility, or use a tree representation. $\endgroup$ – Raphael May 6 '17 at 7:24
  • $\begingroup$ True, thanks for pointing that out - I guess its just the same, but without the Kleene star (unless there are more operations that represent more than a single specified number of repetitions) I am however not familiar with any research on this. $\endgroup$ – IARI May 6 '17 at 9:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't repetition part of EBNF? $\endgroup$ – Raphael May 6 '17 at 7:25
  • $\begingroup$ @Raphael, it's a different kind of repetition. Here we want all of the repeats to be the same exact string (which must be produced by the terminal $B$). EBNF allows each repeat to be a different string, as long as it matches the terminal $B$. (Also I think EBNF doesn't let you specify the number of repetitions, so it's basically like $*$ in a regular expression.) $\endgroup$ – D.W. May 6 '17 at 16:40
  • 2
    $\begingroup$ I suppose its worth to mention, that minimal representations are not unique in general: consider the word $ABABCBC$. Thanks to Matthias Heizman for raising the question. $\endgroup$ – IARI May 7 '17 at 19:08
  • $\begingroup$ @D.W. Ah, right. I thought that since regexps usually have fixed-range repetition EBNF would have it, too. $\endgroup$ – Raphael May 7 '17 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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