A method for transforming grammars into LL(k) form

Summary A new method for transforming grammars into equivalent LL(k) grammars is studied. The applicability of the transformation is characterized by defining a subclass of LR(k) grammars, called predictive LR(k) grammars, with the property that a grammar is predictive LR(k) if and only if the corresponding transformed grammar is LL(k). Furthermore, it is shown that deterministic bottom-up parsing of a predictive LR(k) grammar can be done by the LL(k) parser of the transformed grammar. This parsing method is possible since the transformed grammar always left-to-right covers the original grammar. The class of predictive LR(k) grammars strictly includes the class of LC(k) grammars (the grammars that can be parsed deterministically in the left-corner manner). Thus our transformation is more powerful than the one previously available, which transforms LC(k) grammars into LL(k) form.     

Electrostatic image theory for two anisotropic half-spaces

An image solution for the canonical electrostatic problem of a point charge in an anisotropic half-space bounded by another anisotropic half-space is presented. The image source is obtained in operator form by using Fourier-transformed Maxwell equations and transmission line theory. After applying Heaviside operator calculus the image operator can be interpreted as a combination of a point charge and a sector of planar charge. The new theory is shown to coincide with the previously known image solutions of less general anisotropic media. In addition to being applicable to any physically feasible anisotropic medium of electrostatics, the method can be used for steady-current conductivity problems via a duality transformation.     

Solving parity games by a reduction to SAT

This paper presents a reduction from the problem of solving parity games to the satisfiability problem in propositional logic (SAT). The reduction is done in two stages, first into difference logic, i.e. SAT combined with the theory of integer differences, an instance of the SAT modulo theories (SMT) framework. In the second stage the integer variables and constraints of the difference logic encoding are replaced with a set of Boolean variables and constraints on them, giving rise to a pure SAT encoding of the problem. The reduction uses Jurdziński?s characterisation of winning strategies via progress measures. The reduction is motivated by the success of SAT solvers in symbolic verification, bounded model checking in particular. The paper reports on prototype implementations of the reductions and presents some experimental results.     

Surrogate-based optimization of a periodic rescheduling algorithm

Periodic rescheduling is an iterative method for real-time decision-making on industrial process operations. The design of such methods involves high-level when-to-schedule and how-to-schedule decisions, the optimal choices of which depend on the operating environment. The evaluation of the choices typically requires computationally costly simulation of the process, which—if not sufficiently efficient—may result in a failure to deploy the system in practice. We propose the continuous control parameter choices, such as the re-optimization frequency and horizon length, to be determined using surrogate-based optimization. We demonstrate the method on real-time rebalancing of a bike sharing system. Our results on three test cases indicate that the method is useful in reducing the computational cost of optimizing an online algorithm in comparison to the full factorial sampling.     

A Microprocessor Controlled System For Photoelectrochemical Measurements

ABSTRACT

An automatic system for measuring photocurrent of electrodes as a function of excitation wavelength and electrode potential is described. Applications to a chemically modified transparent Sn0₂ electrode and an oxide-covered tantalum electrode are shown.     

On-line construction of suffix trees

An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It always has the suffix tree for the scanned part of the string ready. The method is developed as a linear-time version of a very simple algorithm for (quadratic size) suffixtries. Regardless of its quadratic worst case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give, in a natural way, the well-known algorithms for constructing suffix automata (DAWGs).This research was supported by the Academy of Finland and by the Alexander von Humboldt Foundation (Germany).     

A Comparision of the Number of Rational Places of Certain Function Fields to the Hasse-Weil Bounds

We give explicitly the number of rational places of certain function fields in terms of the reciprocals of the zeros of the function fields in question. The results are then compared with the Hasse-Weil bounds by using the approximation theorems of Dirichlet and Kronecker and it turns out that in many of these function fields the number of rational places is near the upper Hasse-Weil bound. Keywords:Function fields, Diophantine approximation, Exponential sums.