The Annual European Meeting of the Association for Symbolic Logic, also known as the Logic Colloquium, is among the most prestigious annual meetings in the field. The current volume, Logic Colloquium ...2007, with contributions from plenary speakers and selected special session speakers, contains both expository and research papers by some of the best logicians in the world. This volume covers many areas of contemporary logic: model theory, proof theory, set theory, and computer science, as well as philosophical logic, including tutorials on cardinal arithmetic, on Pillay's conjecture, and on automatic structures. This volume will be invaluable for experts as well as those interested in an overview of central contemporary themes in mathematical logic.
This work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypotheses space chosen for the class. In subsequent investigations, uniformly recursively enumerable ...hypotheses spaces have been considered. In the present work, the following four types of learning are distinguished: class-comprising (where the learner can choose a uniformly recursively enumerable superclass as hypotheses space), class-preserving (where the learner has to choose a uniformly recursively enumerable hypotheses space of the same class), prescribed (where there must be a learner for every uniformly recursively enumerable hypotheses space of the same class) and uniform (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). While for explanatory learning, these four types of learnability coincide, some or all are different for other learning criteria. For example, for conservative learning, all four types are different. Several results are obtained for vacillatory and behaviourally correct learning; three of the four types can be separated, however the relation between prescribed and uniform learning remains open. It is also shown that every (not necessarily uniformly recursively enumerable) behaviourally correct learnable class has a prudent learner, that is, a learner using a hypotheses space such that it learns every set in the hypotheses space. Moreover the prudent learner can be effectively built from any learner for the class.
The present work is dedicated to the study of modes of data-presentation in the range between text and informant within the framework of inductive inference. In this study, the learner alternatingly ...requests sequences of positive and negative data. We define various formalizations of valid data presentations in such a scenario. We resolve the relationships between these different formalizations, and show that one of these is equivalent to learning from informant. We also show a hierarchy formed (for each of the formalizations studied) by considering the number of switches between requests for positive and negative data.
The present work determines the exact nature of linear time computable notions which characterise automatic functions (those whose graphs are recognised by a finite automaton). The paper also ...determines which type of linear time notions permit full learnability for learning in the limit of automatic classes (families of languages which are uniformly recognised by a finite automaton). In particular it is shown that a function is automatic iff there is a one-tape Turing machine with a left end which computes the function in linear time where the input before the computation and the output after the computation both start at the left end. It is known that learners realised as automatic update functions are restrictive for learning. In the present work it is shown that one can overcome the problem by providing work-tapes additional to a resource-bounded base tape while keeping the update-time to be linear in the length of the largest datum seen so far. In this model, one additional such worktape provides additional learning power over the automatic learner model and the two-work-tape model gives full learning power.
In this paper it is studied for which oracles A and which types of A-r.e. matroids the class of all A-r.e. closed sets in the matroid is learnable by an unrelativised learner. The learning criteria ...considered comprise in particular criteria more general than behaviourally correct learning, namely behaviourally correct learning from recursive texts, partial learning and reliably partial learning. For various natural classes of matroids and learning criteria, characterisations of learnability are obtained.
Part 1 Introduction: Stent insertion to palliate malignant dysphagia is becoming more common as the incidence of oesophageal cancer rises and there are several studies demonstrating the effectiveness ...of this technique in improving symptoms. However, palliation of dysphagia may be incomplete, poor or become a recurrent need. Upper gastrointestinal endoscopy forms the mainstay of both investigation and treatment for these patients but it is invasive, has a morbidity and mortality attached and does not always aid in the diagnosis of inadequately palliated or recurrent dysphagia, which is sometimes due to disordered motility and not loss of luminal patency. Methodology: Using oesophageal scintigraphy we first validated the technique in ten normal controls on two separate occasions and then applied the technique to patients before and one month after oesophageal stenting. In addition, other objective measurements including weight loss, body fat, quality of life and swallow scores were recorded in order to assess the validity of the technique for the longer term follow up of patients being treated for inoperable oesophageal cancer. Results: It was found that the technique was valid and reproducible in normal subjects and, when applied to patients with oesophageal cancer it was well tole~ated and that the percentage distance covered in 10 and 30 seconds was a measure of luminal patency and regional dysmotility respectively. Whilst stenting demonstrably improved oesophageal transit in most cases this was mirrored by an arrest in decline, rather than an improvement in quality of life scores. Conclusions: Oesophageal scintigraphy is a well . tolerated technique for assessing swallowing in health and disease but has limited practical applications as no effective treatments currently exist for the treatment of regional dysmotility in cancer. Arising from this work we have developed a novel technique that allows for the quantitative investigation and follow up of patients with delayed oesophageal transit based upon oesophageal scintigraphy and subsequent data analysis using image analysis and 3-D graphing software. The term given to this was 'Functional Oesophageal Mapping' and the process is described in detail and a clinical example given. Part 2 Introduction: We tested the hypothesis that HER-2 protein over-expression occurs in oesophageal adenocarcinoma and that this is associated with HER-2 gene amplification, histopathological tumour characteristics and clinical outcome, similar to the situation in breast cancer. Methodology: Blocks from 100 resected oesophageal adenocarcinoma specimens were retrieved and stained for the presence of c-erbB-2 protein using immunohistochemistry and HER-2 gene amplification using fluorescence in situ hybridization respectively. These are the same kits that are used in FDA-approved methods for predicting trastuzumab response in breast cancer. A minimum of five years of clinical follow up was available and patient demographic information was recorded in all the cases. Histopathological tumour and patient characteristics and survival were determined. Results: The survival of groups with chromosome 17 polyploidy and HER-2 gene amplification was significantly worse than groups that were diploid for chromosome 17 without HER-2 amplification Conclusions: The reduced survival in patients with chromosome 17 polyploidy and with HER-2 gene amplification suggests an avenue for additional treatments in these cases with trastuzumab (Herceptin). This is currently used in patients with breast cancers displaying similar characteristics.
Enumerations of the Kolmogorov function Beigel, Richard; Buhrman, Harry; Fejer, Peter ...
The Journal of symbolic logic,
06/2006, Volume:
71, Issue:
2
Journal Article
Peer reviewed
Open access
A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among ...the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP.
In the theory of algorithmic randomness, one of the central notions is that of computable randomness. An infinite binary sequence X is computably random if no recursive martingale (strategy) can win ...an infinite amount of money by betting on the values of the bits of X. In the classical model, the martingales considered are real-valued, that is, the bets made by the martingale can be arbitrary real numbers. In this paper, we investigate a more restricted model, where only integer-valued martingales are considered, and we study the class of random sequences induced by this model.
PDF
