Abstract

Abstract
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.

Abstract
An efficient traffic-network is an essential demand for any smart city. Usually, city traffic forms a huge network with millions of locations and trips. Traffic flow prediction using such large data is a classical problem in intelligent transportation system (ITS). Many existing models such as ARIMA, SVR, ANN etc, are deployed to retrieve important characteristics of traffic-network and for forecasting mobility. However, these methods suffer from the inability to handle higher data dimensionality. The tensor-based approach has recently gained success over the existing methods due to its ability to decompose high dimension data into factor components. We present a modified Tucker decomposition method which predicts traffic mobility by approximating very large networks so as to handle the dimensionality problem. Our experiments on two big-city traffic-networks show that our method reduces the forecasting error, for up to 7 days, by around 80% as compared to the existing state of the art methods. Further, our method also efficiently handles the data dimensionality problem as compared to the existing methods. © 2018, Springer Nature Switzerland AG.

Abstract

Abstract

Abstract