by Chi-lok Chan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Scheduling Problems of Chain-like Task System --- p.4 / Chapter 2.1 --- Introduction --- p.4 / Chapter 2.2 --- Problem Assumptions and Notations Definition --- p.7 / Chapter 2.3 --- Related Works --- p.9 / Chapter 2.3.1 --- Bokhari's Algorithm --- p.10 / Chapter 2.3.2 --- Sheu and Chiang's Algorithm --- p.12 / Chapter 2.3.3 --- Hsu's Algorithm --- p.12 / Chapter 2.4 --- Decision Algorithms for Un-mergeable Task System --- p.18 / Chapter 2.4.1 --- Feasible Length-K Schedule --- p.18 / Chapter 2.4.2 --- Generalized Decision Test --- p.23 / Chapter 2.5 --- Dominated and Non-dominated Task Systems --- p.26 / Chapter 2.5.1 --- Algorithm for Dominated Task System --- p.26 / Chapter 2.5.2 --- Property of Non-dominated Task System --- p.27 / Chapter 2.6 --- A Searching-Based Algorithm for the Optimization Problem --- p.28 / Chapter 2.6.1 --- Algorithm --- p.29 / Chapter 2.6.2 --- Complexity Analysis --- p.31 / Chapter 2.7 --- A Searching Algorithm Based on a Sorted Matrix --- p.33 / Chapter 2.7.1 --- Sorted Matrix --- p.33 / Chapter 2.7.2 --- Algorithm for the Optimization Problem --- p.35 / Chapter 2.7.3 --- Complexity Analysis --- p.40 / Chapter 2.8 --- A Constructive Algorithm for the Optimization Problem --- p.43 / Chapter 2.9 --- A Modified Constructive Algorithm --- p.46 / Chapter 2.9.1 --- Algorithm --- p.46 / Chapter 2.9.2 --- Worst-Case Analysis --- p.50 / Chapter 2.9.3 --- Sufficient Condition for Efficient Algorithm H --- p.58 / Chapter 2.9.4 --- Average-Case Analysis --- p.62 / Chapter 2.10 --- Performance Evaluation --- p.65 / Chapter 2.10.1 --- Optimal Schedule --- p.65 / Chapter 2.10.2 --- Space Complexity Analysis --- p.67 / Chapter 2.10.3 --- Time Complexity Analysis --- p.68 / Chapter 2.10.4 --- Simulation of Algorithm F and Algorithm H --- p.70 / Chapter 2.11 --- Conclusion --- p.74 / Chapter 3 --- Vehicle Scheduling Problems with Time Window Constraints --- p.77 / Chapter 3.1 --- Introduction --- p.77 / Chapter 3.2 --- Problem Formulation and Notations --- p.79 / Chapter 3.3 --- NP-hardness of VSP-WINDOW-SLP --- p.83 / Chapter 3.3.1 --- A Transformation from PARTITION --- p.83 / Chapter 3.3.2 --- Intuitive Idea of the Reduction --- p.85 / Chapter 3.3.3 --- NP-completeness Proof --- p.87 / Chapter 3.4 --- Polynomial Time Algorithm for the VSP-WINDOW on a Straight Line with Common Ready Time --- p.98 / Chapter 3.5 --- Strong NP-hardness of VSP-WINDOW-TREEP --- p.106 / Chapter 3.5.1 --- A Transformation from 3-PARTITION --- p.107 / Chapter 3.5.2 --- NP-completeness Proof --- p.107 / Chapter 3.6 --- Conclusion --- p.111 / Chapter 4 --- Conclusion --- p.115 / Bibliography --- p.119

Languages evolve, adapting to pressures arising from their learning and use. As these pressures may be different in different sociocultural environments, non-linguistic factors relating to the group structure of the people who speak a language may influence the features of the language itself. Identifying such factors, and the mechanisms by which they operate, would account for some of the diversity seen in the complexity of different languages. This thesis considers two key hypotheses which connect group structure to complex language features and evaluates them experimentally. Firstly, languages spoken by greater numbers of people are thought to be less morphologically complex than those employed by smaller groups. I assess two mechanisms by which group size could have such an effect: different degrees of variability in the linguistic input learners receive, and the effects of adult learning. Four experiments conclude that there is no evidence for different degrees of speaker input variability having any effect on the cross-generational transmission of complex morphology, and so no evidence for it being an explanation for the effect of population size on linguistic complexity. Three more experiments conclude that adult learning is a more likely mechanism, but that linking morphological simplification at the level of the individual to group-level characteristics of a language cannot be simply explained. Idiosyncratic simplifications of adult learners, when mixed with input from native speakers, may result in the linguistic input for subsequent learners being itself complex and variable, preventing simplified features from becoming more widespread. Native speaker accommodation, however, may be a key linking mechanism. Speakers of a more complex variant of a language simplify their language to facilitate communication with speakers of a simpler language. In doing so, they may increase the frequency of particular simplifications in the input of following learners. Secondly, esoteric communication | that carried out by smaller groups in which large amounts of information is shared and in which adult learning is absent | may provide the circumstances necessary for the generation and maintenance of more complex features. I assess this in four experiments. Without a learnability pressure, esoteric communication illustrates how complexity can be maintained, but there is generally no evidence of how smaller groups or those with greater amounts of shared information would develop comparatively more complex features. Any observable differences in the complexity of the languages of different types of groups is eliminated through repeated interaction between group members. There is, however, some indication that the languages used by larger groups may be more transparent, and so easier for adult learners to understand.

Although group-living is widespread in animals, the degree of social complexity varies markedly within and among taxa. One important precondition for the evolution of higher forms of social complexity is increasing group size. However, this imposes a challenge: finding sufficient food for growing numbers of individuals. One hypothesis is that the (in)ability to avoid resource competition as group size increases, could partly explain variation in social complexity among vertebrates. Increasingly, evidence suggests that resource competition can be reduced via three forms of individual specialisation. These are foraging niche specialisation, specialisation to a role under division of labour (DoL), and as a mediator of these two, personality variation. Yet few studies have directly investigated the role of these specialisations in mediating the costs of increasing group size in social vertebrates. In this thesis, I first review the evidence to date that specialising to a foraging niche, and/or to a task under DoL, is (1) mediated via personality variation and (2) can be a means of reducing competition, generated by increasing group size, in social species (Chapter 2). Then, using the cooperative breeding chestnut-crowned babbler (Pomatostomus ruficeps) as my model system, I empirically test some of the hypotheses posed in this review, regarding foraging niche specialisation and associations with personality variation. In Chapter 3, I show that babblers do show personality variation in traits likely to facilitate niche segregation, and in Chapter 4 that variation among individuals within groups is sufficient to lead to intragroup niche specialisation. However, I find that the level of variation within groups is not associated with group size. Then in Chapter 5, I show that in a direct measure of foraging niche, there is only limited evidence for intragroup specialisation, and again that any specialisation is not associated with larger group sizes. I therefore find no evidence that niche specialisation is a means through which babblers can overcome the costs of increasing group size. I discuss the implications of these results for the rise of social complexity in this system, and social vertebrates generally.

A Boolean matrix is a matrix with elements from the Boolean semiring ({0, 1}, +, x), where the addition and multiplication are as usual with the exception that 1 + 1 = 1. In this thesis we study eight classes of monoids whose elements are Boolean matrices. Green's relations are five equivalence relations and three pre-orders which are defined on an arbitrary monoid M and describe much of its structure. In the monoids we consider the equivalence relations are uninteresting - and in most cases completely trivial - but the pre-orders are not and play a vital part in understanding the structure of the monoids. Each of the three pre-orders in each of the eight classes of monoids can be viewed as a computational decision problem: given two elements of the monoid, are they related by the pre-order? The main focus of this thesis is determining the computational complexity of each of these twenty-four decision problems, which we successfully do for all but one.

Cette thèse étudie des formalismes logiques exprimant des propriétés sur des programmes. L'intention originale de ces logiques est de vérifier formellement la correction de programmes manipulant des pointeurs. Dans l'ensemble, il ne sera pas proposé de méthode de vérification applicable dans cette thèse- nous donnons plutôt un éclairage nouveau sur la logique de séparation, une logique pour triplets de Hoare. Pour certains fragments essentiels de cette logique, la complexité et la décidabilité du problème de la satisfiabilité n'étaient pas connus avant ce travail. Aussi, sa combinaison avec certaines autres méthodes de vérification était peu étudiée. D'une part, dans ce travail nous isolons l'opérateur de la logique de séparation qui la rend indécidable. Nous décrivons le pouvoir expressif de cette logique, en la comparant à des logiques du second ordre. D'autre part, nous essayons d'étendre des fragments décidables de la logique de séparation avec la une logique temporelle et avec l'aptitude à décrire les données. Cela nous permet de donner des limites à l'utilisation de la logique de séparation. En particulier, nous donnons des limites à la création de logiques décidables utilisant ce formalisme combiné à une logique temporelle ou à l'aptitude à décrire les données. / This thesis studies logics which express properties on programs. These logics were originally intended for the formal verification of programs with pointers. Overall, no automated verification method will be proved tractable here- rather, we give a new insight on separation logic. The complexity and decidability of some essential fragments of this logic for Hoare triples were not known before this work. Also, its combination with some other verification methods was little studied. Firstly, in this work we isolate the operator of separation logic which makes it undecidable. We describe the expressive power of this logic, comparing it to second-order logics. Secondly, we try to extend decidable subsets of separation logic with a temporal logic, and with the ability to describe data. This allows us to give boundaries to the use of separation logic. In particular, we give boundaries to the creation of decidable logics using this logic combined with a temporal logic or with the ability to describe data.

O adolescente, ao se deparar com o adoecimento pelo câncer, se vê diante de um grande desafio que desencadeia grandes transformações em sua vida. As limitações impostas pela doença alteram a rotina dos adolescentes que se veem forçados a se submeter a um tratamento agressivo e doloroso e a se adaptar às restrições tanto de atividades quanto de relacionamentos. O objetivo da presente investigação é compreender como se configura o cuidado do adolescente com câncer, articulando as perspectivas dos adolescentes, familiares e da equipe de saúde, no contexto de um hospital de nível terciário de atenção, e apontar elementos que se aproximam e se distanciam de um cuidado que considere a complexidade humana. Foi utilizada a abordagem metodológica qualitativa, com fundamentação nas ideias acerca do pensamento complexo, tratado por Edgar Morin, pensador francês, que defende a necessidade de um modo de pensar multidimensional, em consonância com a complexidade da realidade. Participaram do estudo 12 adolescentes (com idade entre 12 e 18 anos), 14 familiares (dois pais, nove mães e três irmãos) além de 37 profissionais (15 médicos, quatro alunos do sexto ano de medicina, seis enfermeiras, cinco auxiliares de enfermagem, uma técnica de enfermagem, duas assistentes sociais, dois psicólogos, uma terapeuta ocupacional e duas nutricionistas). A entrevista e a observação foram utilizadas para a coleta de dados. A análise compreensiva dos dados foi desenvolvida buscando preservar a sua característica multidimensional, mediante a articulação dos diferentes sujeitos, considerando as distintas perspectivas, envolvidas no contexto do estudo, bem como o conjunto e suas relações, reconhecendo a complexidade do todo. Foram construídas três temáticas, inter-relacionando os dados empíricos com o referencial teórico proposto: a dialógica racionalidade-afetividade, a dialógica vida-morte e a dialógica indivíduoequipe- instituição no cuidado do adolescente com câncer. Considerando a questão do cuidado do adolescente com câncer como um fenômeno complexo que envolve múltiplas dimensões (indivíduos em um momento peculiar de seu desenvolvimento, com demandas específicas, inseridos em uma unidade familiar e social, vivenciando uma doença grave que os aproxima cotidianamente de uma equipe de profissionais com diferentes formações e diversos enfoques no cuidado), cabe construir práticas de cuidar condizentes com a complexidade da condição humana. Deste modo, cabe integrar a racionalidade técnica com a realidade vivida que comporta também a afetividade, a religiosidade, a angústia existencial e a possibilidade da criação, algumas das condições próprias do sujeito humano. / When faced with cancer, adolescents are confronted with a big challenge that leads to great transformations in their lives. The limitations the disease imposes alter the adolescents\' routine, who are forced to submit to an aggressive and painful treatment and to adapt to restrictions in their activities and relationships. This research aims to understand care delivery to adolescents with cancer, articulating the perspectives of adolescents, relatives and the health team in the context of a tertiary care hospital, as well as to appoint elements that approach and get away from care that takes into account human complexity. A qualitative methodological approach was used, based on the ideas of complex thinking according to the French thinker Edgar Morin, who defends the need for a multidimensional way of thinking, in line with the complexity of reality. Study participants were 12 adolescents (between 12 and 18 years old), 14 relatives (two fathers, nine mothers and three siblings), besides 37 professionals (15 physicians, four sixth-year medical school students, six nurses, five nursing auxiliaries, one nursing technician, two social workers, two psychologists, one occupational therapist and two nutritionists). Interview and observation were used for data collection. Comprehensive data analysis was developed in the attempt to preserve its multidimensional nature, through the articulation among different subjects, considering the distinct perspectives involved in the study context, as well as the collective picture and its relations, acknowledging the complexity of the whole. Three themes were constructed, interrelating empirical data with the proposed theoretical framework: the rationality-affectivity dialogue, the life-death dialogue and the individual-team-institution dialogue in care for adolescents with cancer. Considering care delivery to adolescents with cancer as a complex phenomenon, involving multiple dimensions (individuals at a peculiar moment in their development, with specific demands, inserted in a family and social unit, experiencing a severe disease, which every data approximates them to a professional theme with different backgrounds and various care foci), care practices should be constructed that are in line with the complexity of the human condition. Thus, technical rationality should be integrated with the experience reality, which also includes affectivity, religiosity, existential anguish and the possibility of creation, which are some of the conditions characteristic of human beings.

Yang, Lin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 57-61). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problems and Main Results --- p.2 / Chapter 1.1.1 --- Firefighting on Trees --- p.2 / Chapter 1.1.2 --- Maximum k-Vertex Cover on Trees --- p.3 / Chapter 1.2 --- Background --- p.3 / Chapter 1.2.1 --- Random Separation --- p.4 / Chapter 1.2.2 --- Kernelization --- p.5 / Chapter 1.2.3 --- Infeasibility of Polynomial Kernel --- p.6 / Chapter 1.3 --- Organization of the Thesis --- p.7 / Chapter 2 --- Firefighting on Trees --- p.9 / Chapter 2.1 --- Definitions and Notation --- p.10 / Chapter 2.2 --- FPT Algorithms --- p.13 / Chapter 2.2.1 --- Saving k Vertices --- p.14 / Chapter 2.2.2 --- Saving k Leaves --- p.19 / Chapter 2.2.3 --- Protecting k Vertices --- p.23 / Chapter 2.3 --- Approximation --- p.29 / Chapter 2.3.1 --- A (1 ´ؤ 1/e)-Approximation Algorithm --- p.29 / Chapter 2.3.2 --- LP-Repsecting Rounding cannot Do Better --- p.33 / Chapter 3 --- Maximum k-Vertex Cover on Trees --- p.38 / Chapter 3.1 --- Maximum k Vertex Cover on Trees --- p.39 / Chapter 3.2 --- k-MVC on Degree Bounded Graphs --- p.45 / Chapter 3.3 --- k-MVC on Degeneracy Bounded Graphs --- p.46 / Chapter 3.4 --- Extension to Maximum k Dominating Set --- p.47 / Chapter 4 --- Conclusion --- p.49 / Chapter 4.1 --- The Firefighter problem --- p.49 / Chapter 4.2 --- The Maximum k-Vertex Cover problem --- p.53 / Acknowledgement --- p.55 / Bibliography --- p.57

Typescript (photocopy). / Digitized by Kansas Correctional Industries

We investigated the association of coping with quality of life (QoL) among parents of children with chronic illnesses, particularly inherited metabolic diseases (IMD); and whether coping may modify the association between caregiving complexity and parental QoL. In project 1, we systematically reviewed studies of parents of children with chronic illness. Among 10 eligible studies, we identified some evidence that adaptive coping strategies were positively associated with parental psychological QoL. In project 2, we analyzed data from a crosssectional mailed Canadian survey of parents of children <12 years of age with IMD. Among 113 respondents, greater emotion-focused coping was associated with lower mental QoL (all parents) and higher depressive symptoms (parents of children >=5 years). Analysis of significant interactions between coping and caregiving complexity did not reveal clear trends. Understanding the association of parental coping with QoL may help to inform interventions to promote parental health as part of family-centred care.

Families of linear functionals on a vector space that are mapped to each other by a group of symmetries of the space have a significant amount of structure. This results in computational redundancies which can be used to make computing the entire family of functionals at once more efficient than applying each in turn. This thesis explores asymptotic complexity results for a few such families: contingency tables and unranked choice data. These are used to explore the framework of Radon transform diagrams, which promise to allow general theorems about linear summary statistics to be stated and proved.