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.

Persistence of income inequality : does child mortality matter?

Many developing countries are afflicted by persistent inequality in the distribution of income. While a growing body of literature emphasizes differential fertility as a channel through which income inequality persists, this paper investigates differential child mortality – differences in the incidence of child mortality across socioeconomic groups – as a critical link in this regard. Using evidence from cross-country data to evaluate this linkage, we find that differential child mortality serves as a stronger channel than differential fertility in the transmission of income inequality over time. We use random effects and generalized estimating equations techniques to account for temporal correlation within countries. The results are robust to the use of an alternate definition of fertility that reflects parental preference for children instead of realized fertility.

On inequality tax evasion and progressive taxes

This paper proposes a simple variation of the Allingham and Sandmo (1972) construct and integrates it to a dynamic general equilibrium framework with heterogeneous agents. We study an overlapping generations framework i n which agents must initially decide whether to evade taxes or not. In the event they decide to evade, they then have to decide the extent of income or wealth they wish to under-report. We find that in comparison with the basic approach, the ‘evade or not’ choice drastically reduced the extent of evasion in the economy. This outcome is the result of an anomaly intrinsic to the basic Allingham and Sandmo version of the model, which makes the evade-or-not extension a more suitable approach to modelling the issue. We also find that the basic model, and the model with and ‘evade-or-not’ choice have strikingly different political economy implications, , which suggest fruitful avenues of empirical research.

Embracing Philosophy and Raising the Standard of Pre-service Teacher Education Programs

In this chapter, a rationale is developed for incorporating philosophy into teacher training programs as a means of both preparing quality teachers for the 21st century and meeting the expectations detailed in the professional standards established by the statutory authority that regulates the profession in Queensland, the Queensland College of Teaching is presented. Furthermore, in-service teachers from Buranda State School, a Brisbane primary school that has been successfully teaching philosophy to its students for over 10 years, shares their experiences of teaching philosophy and how it has enhanced student learning and the quality of teaching and professionalism of the teachers. Finally, the implications of embedding philosophy into teacher training programs are explored in terms of developing the personal integrity of beginning teachers.

Automatic generation of assertions to detect potential security vulnerabilities in C programs that use union and pointer types

Type unions, pointer variables and function pointers are a long standing source of subtle security bugs in C program code. Their use can lead to hard-to-diagnose crashes or exploitable vulnerabilities that allow an attacker to attain privileged access over classified data. This paper describes an automatable framework for detecting such weaknesses in C programs statically, where possible, and for generating assertions that will detect them dynamically, in other cases. Exclusively based on analysis of the source code, it identifies required assertions using a type inference system supported by a custom made symbol table. In our preliminary findings, our type system was able to infer the correct type of unions in different scopes, without manual code annotations or rewriting. Whenever an evaluation is not possible or is difficult to resolve, appropriate runtime assertions are formed and inserted into the source code. The approach is demonstrated via a prototype C analysis tool.

Inhibitors to optimal project portfolio selection

The selection of projects and programs of work is a key function of both public and private sector organisations. Ideally, projects and programs that are selected to be undertaken are consistent with strategic objectives for the organisation; will provide value for money and return on investment; will be adequately resourced and prioritised; will not compete with general operations for resources and not restrict the ability of operations to provide income to the organisation; will match the capacity and capability of the organisation to deliver; and will produce outputs that are willingly accepted by end users and customers. Unfortunately,this is not always the case. Possible inhibitors to optimal project portfolio selection include: processes that are inconsistent with the needs of the organisation; reluctance to use an approach that may not produce predetermined preferences; loss of control and perceived decision making power; reliance on quantitative methods rather than qualitative methods for justification; ineffective project and program sponsorship; unclear project governance, processes and linkage to business strategies; ignorance, taboos and perceived effectiveness; inadequate education and training about the processes and their importance.