An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L(Γ*), and outputs a string in L(Γ*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L(Γ*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.

Recently, Global navigation satellite system (GNSS) positioning has been widely used in various applications (e.g. car navigation system, smartphone map application, autonomous driving). In GNSS positioning, coordinates are calculated from observed satellite signals. The observed signals contain various errors, so the calculated coordinates also have some errors. Double-difference is one of the widely used ideas to reduce the errors of the observed signals. Although double-difference can remove many kinds of errors from the observed signals, some errors still remain (e.g. multipath error). In this paper, we define the remaining error as “double-difference-error (DDE)” and propose a method for estimating DDE using machine learning. In addition, we attempt to improve DGNSS positioning by feeding back the estimated DDE. Previous research applying machine learning to GNSS has focused on classifying whether the signal is LOS (Line Of Sight) or NLOS (Non Line Of Sight), and there is no study that attempts to estimate the amount of error itself as far as we know. Furthermore, previous studies had the limitation that their dataset was recorded at only a few locations in the same city. This is because these studies are mainly aimed at improving the positioning accuracy of vehicles, and collecting large amounts of data using vehicles is costly. To avoid this problem, in this research, we use a huge amount of openly available stationary point data for training. Through the experiments, we confirmed that the proposed method can reduce the DGNSS positioning error. Even though the DDE estimator was trained only on stationary point data, the proposed method improved the DGNSS positioning accuracy not only with stationary point but also with mobile rover. In addition, by comparing with the previous (detect and remove) approach, we confirmed the effectiveness of the DDE feedback approach.