Some applications of logic to feasibility in higher types

While it is commonly accepted that computability on a Turing machine in polynomial time represents a correct formalization of the notion of a feasibly computable function, there is no similar agreement on how to extend this notion on functionals, that is, what functionals should be considered feasible. One possible paradigm was introduced by Mehlhorn, who extended Cobham's definition of feasible functions to type 2 functionals. Subsequently, this class of functionals (with inessential changes of the definition) was studied by Townsend who calls this class POLY, and by Kapron and Cook who call the same class basic feasible functionals. Kapron and Cook gave an oracle Turing machine model characterisation of this class. In this article, we demonstrate that the class of basic feasible functionals has recursion theoretic properties which naturally generalise the corresponding properties of the class of feasible functions, thus giving further evidence that the notion of feasibility of functionals mentioned above is correctly chosen. We also improve the Kapron and Cook result on machine representation.Our proofs are based on essential applications of logic. We introduce a weak fragment of second order arithmetic with second order variables ranging over functions from NN which suitably characterises basic feasible functionals, and show that it is a useful tool for investigating the properties of basic feasible functionals. In particular, we provide an example how one can extract feasible programs from mathematical proofs that use nonfeasible functions.

Mind change complexity of learning logic programs

The present paper motivates the study of mind change complexity for learning minimal models of length-bounded logic programs. It establishes ordinal mind change complexity bounds for learnability of these classes both from positive facts and from positive and negative facts. Building on Angluin’s notion of finite thickness and Wright’s work on finite elasticity, Shinohara defined the property of bounded finite thickness to give a sufficient condition for learnability of indexed families of computable languages from positive data. This paper shows that an effective version of Shinohara’s notion of bounded finite thickness gives sufficient conditions for learnability with ordinal mind change bound, both in the context of learnability from positive data and for learnability from complete (both positive and negative) data. Let Omega be a notation for the first limit ordinal. Then, it is shown that if a language defining framework yields a uniformly decidable family of languages and has effective bounded finite thickness, then for each natural number m >0, the class of languages defined by formal systems of length <= m: • is identifiable in the limit from positive data with a mind change bound of Omega (power)m; • is identifiable in the limit from both positive and negative data with an ordinal mind change bound of Omega × m. The above sufficient conditions are employed to give an ordinal mind change bound for learnability of minimal models of various classes of length-bounded Prolog programs, including Shapiro’s linear programs, Arimura and Shinohara’s depth-bounded linearly covering programs, and Krishna Rao’s depth-bounded linearly moded programs. It is also noted that the bound for learning from positive data is tight for the example classes considered.

Molecular epidemiology of respiratory viruses in a paediatric cohort from Indonesia

Acute lower respiratory tract infections (ALRTIs) are a common cause of morbidity and mortality among children under 5 years of age and are found worldwide, with pneumonia as the most severe manifestation. Although the incidence of severe disease varies both between individuals and countries, there is still no clear understanding of what causes this variation. Studies of community-acquired pneumonia (CAP) have traditionally not focused on viral causes of disease due to a paucity of diagnostic tools. However, with the emergence of molecular techniques, it is now known that viruses outnumber bacteria as the etiological agents of childhood CAP, especially in children under 2 years of age. The main objective of this study was to investigate viruses contributing to disease severity in cases of childhood ALRTI, using a two year cohort study following 2014 infants and children enrolled in Bandung, Indonesia. A total of 352 nasopharyngeal washes collected from 256 paediatric ALRTI patients were used for analysis. A subset of samples was screened using a novel microarray pathogen detection method that identified respiratory syncytial virus (RSV), human metapneumovirus (hMPV) and human rhinovirus (HRV) in the samples. Real-time RT-PCR was used both for confirming and quantifying viruses found in the nasopharyngeal samples. Viral copy numbers were determined and normalised to the numbers of human cells collected with the use of 18S rRNA. Molecular epidemiology was performed for RSV A and hMPV using sequences to the glycoprotein gene and nucleoprotein gene respectively, to determine genotypes circulating in this Indonesian paediatric cohort. This study found that HRV (119/352; 33.8%) was the most common virus detected as the cause of respiratory tract infections in this cohort, followed by the viral pathogens RSV A (73/352; 20.7%), hMPV (30/352; 8.5%) and RSV B (12/352; 3.4%). Co-infections of more than two viruses were detected in 31 episodes (defined as an infection which occurred more than two weeks apart), accounting for 8.8% of the 352 samples tested or 15.4% of the 201 episodes with at least one virus detected. RSV A genotypes circulating in this population were predominantly GA2, GA5 and GA7, while hMPV genotypes circulating were mainly A2a (27/30; 90.0%), B2 (2/30; 6.7%) and A1 (1/30; 3.3%). This study found no evidence of disease severity associated either with a specific virus or viral strain, or with viral load. However, this study did find a significant association with co-infection of RSV A and HRV with severe disease (P = 0.006), suggesting that this may be a novel cause of severe disease.

Fuzzy logic power system stabilizer in multimachine stability studies

Power system stabilizers (PSS) work well at the particular network configuration and steady state conditions for which they were designed. Once conditions change, their performance degrades. This can be overcome by an intelligent nonlinear PSS based on fuzzy logic. Such a fuzzy logic power system stabilizer (FLPSS) is developed, using speed and power deviation as inputs, and provides an auxiliary signal for the excitation system of a synchronous motor in a multimachine power system environment. The FLPSS's effect on the system damping is then compared with a conventional power system stabilizer's (CPSS) effect on the system. The results demonstrate an improved system performance with the FLPSS and also that the FLPSS is robust

Fuzzy logic traffic control at a road junction with time-varying flow rates

Fuzzy logic has been applied to control traffic at road junctions. A simple controller with one fixed rule-set is inadequate to minimise delays when traffic flow rate is time-varying and likely to span a wide range. To achieve better control, fuzzy rules adapted to the current traffic conditions are used.

Hierarchical fuzzy logic traffic control at a road junction

Traffic control at road junctions is one of the major concerns in most metropolitan cities. Controllers of various approaches are available and the required control action is the effective green-time assigned to each traffic stream within a traffic-light cycle. The application of fuzzy logic provides the controller with the capability to handle uncertain natures of the system, such as drivers’ behaviour and random arrivals of vehicles. When turning traffic is allowed at the junction, the number of phases in the traffic-light cycle increases. The additional input variables inevitably complicate the controller and hence slow down the decision-making process, which is critical in this real-time control problem. In this paper, a hierarchical fuzzy logic controller is proposed to tackle this traffic control problem at a 2-way road junction with turning traffic. The two levels of fuzzy logic controllers devise the minimum effective green-time and fine-tune it respectively at each phase of a traffic-light cycle. The complexity of the controller at each level is reduced with smaller rule-set. The performance of this hierarchical controller is examined by comparison with a fixed-time controller under various traffic conditions. Substantial delay reduction has been achieved as a result and the performance and limitation of the controller will be discussed.

Hierarchical fuzzy logic traffic control at a road junction using genetic algorithms

Traffic control at a road junction by a complex fuzzy logic controller is investigated. The increase in the complexity of junction means more number of input variables must be taken into account, which will increase the number of fuzzy rules in the system. A hierarchical fuzzy logic controller is introduced to reduce the number of rules. Besides, the increase in the complexity of the controller makes formulation of the fuzzy rules difficult. A genetic algorithm based off-line leaning algorithm is employed to generate the fuzzy rules. The learning algorithm uses constant flow-rates as training sets. The system is tested by both constant and time-varying flow-rates. Simulation results show that the proposed controller produces lower average delay than a fixed-time controller does under various traffic conditions.