Dynamic Membership for Regular Languages

Setting

• A word of fixed length \(n>0\) …
• … over a fixed size alphabet \(\Sigma=\{a,b,c,\ldots\}\)
• but the word is dynamic

A first (inefficient) algorithm

• Given a regular language \(L\) – e.g. \((ab)^*\)

• Execute at each update a deterministic automaton:

• Incremental Complexity: \(O(n)\)

To summarize

• The dynamic word problem for regular languages:
  • All regular languages are in \(O(\frac{\log n}{\log\log n})\)
  • Some are in \(O(1)\) – e.g. \((ab)^*\)
  • Some are in \(O(\log\log n)\) – e.g. \((ac^*b+c)^*\)
  • Some are in \(\Omega(\frac{\log n}{\log\log n})\) – e.g. \((ab^*a+b)^*c\Sigma^*\)

The algebraic method

• Aim to understand properties on regular languages.

• Syntactic properties:

  • Is it definable in some logics under some syntactic restrictions? – e.g. \(\text{first-order logic}\)

• Computability properties:

  • Is it computable with this very nice restriction/modification of the automata model? – e.g. \(\text{2wpo-automata}\)

• Complexity properties:

  • Does the language belong to some complexity class? –e.g. \(\textrm{AC}^0\)

Co-example

• \(L = (aa)^* c a^*\) is in \(O(1)\)
• \(K = (ab^*a + b)^* c (a+b)^*\) is in \(\Omega(\frac{\log n}{\log \log n})\)
• \(\psi\colon \begin{cases}b\mapsto \epsilon\\ \sigma\mapsto \sigma\text{ otherwise }\end{cases}\)
• \(K = \psi^{-1}(L)\)

The monoid simplification

• \(M\) is a fixed finite monoid
• The dynamic word problem for the monoid \(M\):
  • a dynamic word in \(M^*\)
  • we maintain its product in \(M\)

Language to monoids

• Given a regular language:
  • We compute its syntactic monoid
  • Execute the best possible algorithm for it
  • \(\to\) The language case reduces in \(O(1)\) to the monoid case
• We use monoid as an intermediate to find the best possible algorithm

What I will present now

• Found missing \(O(1)\)-cases
• Up to some conjecture, we have them all.
• Found all regular languages in \(O(\log\log n)\), closing the gap of Frandsen et al.
• Extend it to regular languages, lifting the monoid simplification.

Nilpotent computation – an example

• \(L=c^* a c^* a c^* b c^*\)

• A \(O(1)\) algorithm:

  • Incremental maintenance of the set of all positions with non-\(c\) letters
  • If this set has cardinality \(3\) check membership to the language.

• Extends to any finite set of words separated by neutral letters

Do we have more monoids in \(O(1)\)?

• It is a colored priority queue:

  • An associative array from \(\mathbb{N} \to E\), with \(E\) finite.
  • \(\text{Add}(k, e)\) and \(\text{Remove}(k)\) operations, \(k\in \mathbb{N}, e\in E\)
  • \(\text{MinColor}\) returns the color associated to the min key.

• A classical priority queue can implement a colored priority queue

• A non-constant lower bound for priority queue is a long-standing open problem.

• A direct application of the equations of \(\mathbf{ZG}\).

• If a monoid is not in \(\mathbf{ZG}\) then: \(O(1)\) reduction colored priority queue

The BAD: \(\mathbf{SG}\)

• Predecessor data structure

  • a set of values \(v\in \mathbb{N}\)
  • \(\text{Add}(v)\), \(\text{Remove}(v)\)
  • \(\text{Predecessor}(v)\) returns the maximal value smaller than \(v\)

• Implemented in \(O(\log\log n)\) with van Emde Boas trees

• We reduce in \(O(1)\) for monoids to \(\textbf{SG}\) to this data structure.

• The proof is technical and based on Green’s relations

• The main technical contribution.

Does it always get the appropriate algorithm?

• Recall that we use monoid as an intermediate to find good algorithm for languages

• The following languages have the same syntactic monoids:

  • \(L = (aa)^* c a^*\) is in \(O(1)\)
  • \(K = (ab^*a + b)^* c (a+b)^*\) is in \(\Omega(\frac{\log n}{\log \log n})\)

• … Not always!

The semigroup case

• Recall that a semigroup is like a monoid but possibly without a neutral element.
• All monoids are semigroups but the converse is not true
• Given a regular languages \(L\)
  • Its syntactic semigroup is the transition functions of nonempty words
• The dynamic word problem for semigroup:
  • We fix a finite semigroup \(S\)
  • We have a dynamic word in \(S^+\)
  • we maintain the total product.

From languages to semigroup

• given a regular language:

  • we compute its syntactic monoid semigroup
  • execute the best possible algorithm for it
  • \(\to\) the language case reduces in \(O(1)\) to the monoid semigroup case

• Algorithm for monoids give algorithm for semigroups:

  • by adding identity to non-monoid semigroup: \(S\mapsto S^1\)

• In the \(O(\log\log n)\), \(S^1\) and \(S\) are \(O(1)\)-equivalent to each other.

• In the \(O(1)\), it is not the case!

Co-example

• Take the semigroup \(S=\{(1, 1), (1, 2), (2, 1), (2, 2), 0\}\) with:
  • \((i, j)\cdot (k, p)=\begin{cases}(i, p)\text{ if }j=k\\0\text{ otherwise}\end{cases}\)
• e.g:
  • \((1, 2)\cdot (1, 2) = 0\)
  • \((1, 2)\cdot(2, 1)\cdot(1, 1) = (1, 1)\)
• The monoid \(S^1\) is not is \(\textbf{ZG}\) but we can find a \(O(1)\) algorithm for \(S\)

Co-example

• Take the semigroup \(S=\{(1, 1), (1, 2), (2, 1), (2, 2), 0\}\) with:

  • \((i, j)\cdot (k, p) = \begin{cases}(i, p)\text{ if }j=k\\0\text{ otherwise}\end{cases}\)

• The product \((i_0, j_0)\cdot (i_1, j_1)\cdots (i_n, j_n)\)

  • is \(0\) if \(j_i\neq i_{i+1}\) for some \(i\)
  • is equal to \((i_0, j_n)\) otherwise

• We can count the sliding windows of size \(2\) and conclude

• It doesn’t work for \(S^1\) because of the neutral element.

Are we over yet?

Conclusion

• Semigroup theory tooling has been surprisingly efficient

• We managed to classify the precise complexity of algorithmic problems parametrized by regular languages

• We have linked algebraic analysis to data-structure complexity

• It is reminiscent of what happens in CSP.

• Is there an algebraic parametrized complexity theory waiting to be discovered?

Open problems

• Is there more hierarchy within \(O(\log \log n)\)?
• Can we extend the framework and the tooling to insertion/deletion (probably yes)
• Can we generalize to non-linear structures?
• How to prove non-constant lower bounds for priority queues in the RAM model?