Hey Bruno, This is mighty interesting and I'll be sure to give it a read as soon as I get the time.
Have you already thought about the practical applications of your finding in the field of parsing? Cheers, Nicolas LAURENT On Mon, 25 Feb 2019 at 17:36, Bruno Loff <bruno.l...@gmail.com> wrote: > 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 >
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
