We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for matching the ith captured subexpression). It is known that such regexes have far more expressive power than the regular expressions defined in formal language theory.

I am interested in the following two categories of arithmetic functions on the unary representation of the natural numbers (i.e., a sequence of $n$ symbols a represents the number $n$):


In the first category, a function is given by a search string, a replace string and an operation Replace All, which substitutes the replace string to any occurrence of the search string. For instance:

  • $\lambda n. 2n$
    • "a"
    • "aa"
  • $\lambda n. \frac{n}{2}$
    • "(a*)\1a?"
    • "\1"
  • $\lambda n. \frac{n}{3}$
    • "(a*)\1\1a?a?"
    • "\1"
  • $\lambda n. n \bmod 2$
    • "(a*)\1(a?)"
    • "\2"
  • Collatz function
    • "(a*)\1$|((a)*)"
    • "\1\2\2\2\3"
  • Smallest divisor greater than 1
    • "(aa+?)\1+$|(a*)"
    • "\1\2"


In the second category, a predicate is given by a regex pattern and an operation Match which tries to match the pattern from the beginning of the input sequence. The output is interpreted as True is the match succeeds, and False otherwise. For instance:

  • is_even
    • "(aa)*$"
  • is_odd
    • "a(aa)*$"
  • is_not_prime (from Neil Kandalgaonkar)
    • "a?$|(aa+)\1+$"


Is it possible to devise a transducer for $\lambda n. n^2$ or an acceptor for is_prime? More generally, which arithmetic functions and predicates can be defined in such a model?

  • $\begingroup$ Can you succinctly describe some version of PCRE? $\endgroup$ – Yuval Filmus Apr 23 '15 at 2:53
  • $\begingroup$ In my examples, regular expression with backreferences. Frankly, I still don't know whether I'm going to use some other features of PCRE like lookahead, lookbehind and recursive patterns. $\endgroup$ – Aristide Apr 23 '15 at 3:02
  • 1
    $\begingroup$ If you don't provide us with the computation model, we can analyze its power. Make up your mind on some simple model. Also, imagine we don't know what "regular expression with backreferences" is, and explain its semantics to us. Start with acceptors. $\endgroup$ – Yuval Filmus Apr 23 '15 at 3:03

Your Answer

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

Browse other questions tagged or ask your own question.