The Computational Power of Parsing Expression Grammars

• Type: Article in International Conference Proceedings Book
• Date: 2018

Authors

Loff, B (Author) FCUP; Nelma Moreira (Author) FCUP; Rogério Reis (Author) FCUP

Conference proceedings International

Title: Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings

Pages: 491-502

22nd International Conference on Developments in Language Theory, DLT 2018

10 September 2018 through 14 September 2018

Indexing

Scopus - 2 Citations

Scientific classification

CORDIS: Physical sciences > Computer science

FOS: Natural sciences > Computer and information sciences ; Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

Other information

Authenticus ID: P-00P-KAY

DOI: 10.1007/978-3-319-98654-8_40

Abstract (EN): We propose a new computational model, the scaffolding automaton, which 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.PEGs are computationally ¿universal¿, in the following sense: take any computable function; then there exists a computable function such that has a PEG.There can be no pumping lemma for PEGs. There is no total computable function A with the following property: for every well-formed PEG G, there exists such that for every string of size the output is in and has |x|.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 steps after reading each input symbol. © 2018, Springer Nature Switzerland AG.

Language: English

Type (Professor's evaluation): Scientific