Hello list members,
I am writing to announce a new paper, entitled "The computational power of
parsing expression grammars". It appears on ArXiv at the address:
https://arxiv.org/abs/1902.08272
Any feedback will be most welcome.
Here is an abstract for the paper:
We propose a new computational model, the scaffolding automaton, and prove
that it exactly characterises the computational power of parsing expression
grammars (PEGs). Using this characterisation we show that:
* PEGs have unexpected power and semantics. We present several PEGs with
surprising behaviour, and languages which, unexpectedly, have PEGs,
including a PEG for the language of palindromes whose length is a power of
two, and a PEG for a ``counting language''.
* We show that PEGs are computationally ``universal'', in the following
sense: take any computable function f:{0,1}^* -> {0,1}^*; then there
exists a computable function g: :{0,1}^* -> N such that the set
{ f(x) #^{g(x)} x | x \in {0,1}^* }
has a PEG (where #^{g(x)} means g(x)-many separator symbols `#'). This
result may be used to construct a PEG language which is complete for P
under logspace reductions.
* We show that there can be no pumping lemma for PEGs. There is no total
computable function A with the following property: for every PEG G, there
exists n_0 such that for every string x \in L(G) of size |x| \ge n_0, the
output y = A(G, x) is in L(G) and has |y| > |x|.
* We show that PEGs are strongly non real-time for Turing machines: There
exists a language with a PEG, such that neither it nor its reverse can be
recognised by any multi-tape online Turing machine which is allowed to do
only o(n/\log n) steps after reading each input symbol.
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
