In this thesis we examine the computational complexity of certain digraph homomorphism problems. A homomorphism between digraphs, denoted by $f: G \to H$, is a mapping from the vertices of $G$ to the vertices of $H$ such that the arcs of $G$ are preserved. The problem of deciding whether a homomorphism to a fixed digraph $H$ exists is known as the $H$-colouring problem. We prove a generalization of a theorem due to Bang-Jensen, Hell and MacGillivray. Their theorem shows that for every semi-complete digraph $H$, $H$-colouring exhibits a dichotomy: $H$-colouring is either polynomial time solvable or it is NP-complete. We show that the class of local tournaments also exhibit a dichotomy. The NP-completeness results are found using direct NP-completeness reductions, indicator and vertex (and arc) sub-indicator constructions. The polynomial cases are handled by appealing to a result of Gutjhar, Woeginger and Welzl: the \underbar{$X$}-graft extension. We also provide a new proof of their result that follows directly from the consistency check. An unexpected result is the existence of unicyclic local tournaments with NP-complete homomorphism problems. During the last decade a new approach to studying the complexity of digraph homomorphism problems has emerged. This approach focuses attention on so-called polymorphisms as a measure of the complexity of a digraph homomorphism problem. For a digraph $H$, a polymorphism of arity $k$ is a homomorphism $f: H^k \to H$. Certain special polymorphisms are conjectured to be the key to understanding $H$-colouring problems. These polymorphisms are known as weak near unanimity functions (WNUFs). A WNUF of arity $k$ is a polymorphism $f: H^k \to H$ such that $f$ is idempotent an $f(y,x,x,\ldots,x)=f(x,y,x,\ldots,x)=f(x,x,y,\ldots,x) = \cdots = f(x,x,x,\ldots,y)$. We prove that a large class of polynomial time $H$-colouring problems all have a $\WNUF$. Furthermore we also prove some non-existence results for $\WNUF$s on certain digraphs. In proving these results, we develop a vertex (and arc) sub-indicator construction as well as an indicator construction in analogy with the ones developed by Hell and Ne{\v{s}}et{\v{r}}il. This is then used to show that all tournaments with at least two cycles do not admit a $\WNUF_k$ for $k>1$. This furnishes a new proof (in the case of tournaments) of the result by Bang-Jensen, Hell and MacGillivray referred to at the start. These results lend some support to the conjecture that $\WNUF$s are the ``right'' functions for measuring the complexity of $H$-colouring problems. We also study a related notion, namely that of an injective homomorphism. A homomorphism $f: G \to H$ is injective if the restriction of $f$ to the in-neighbours of every vertex in $G$ is an injective mapping. In order to classify the complexity of these problems we develop an indicator construction that is suited to injective homomorphism problems. For this type of digraph homomorphism problem we consider two cases: reflexive and irreflexive targets. In the case of reflexive targets we are able to classify all injective homomorphism problems as either belonging to the class of polynomial time solvable problems or as being NP-complete. Irreflexive targets pose more of a problem. The problem lies with targets of maximum in-degree equal to two. Targets with maximum in-degree one are polynomial, while targets with in-degree at least three are NP-complete. There is a transformation from (ordinary) graph homomorphism problems to injective, in-degree two, homomorphism problems (a reverse transformation also exists). This transformation provides some explanation as to the difficulty of the in-degree two case. We nonetheless classify all injective homomorphisms to irreflexive tournaments as either being a problem in P or a problem in the class of NP-complete problems. We also discuss some upper bounds on the injective oriented irreflexive (reflexive) chromatic number.

Workload and complexity measures are, as of today, often imprecise and subjective. Currently, two commonly used workload and complexity measuring formulas are Monitor Alert Parameter and the “Bars”, both using the same measurement variables; amount of aircraft and time. This study creates formulas for quantifying ATC complexity. The study is done in an approach environment and is developed and tested on Stockholm TMA by the creation of 20 traffic scenarios. Ten air traffic controllers working in Stockholm TMA studied the complexity of the scenarios individually and ranked the scenarios in reference to each other. Five controllers evaluated scenario A1-A10. These scenarios were used as references when creating the formulas. The other half of the scenarios, B1-B10, ranked by another five controllers, was used as validation scenarios. Factors relevant to an approach environment were identified, and the data from the scenarios were extracted according to the identified factors. Moreover, a regression analysis was made with the ambition to reveal appropriate weights for each variable. At the first regression, called formula #1, some parameter values were identical. Also, some parameter weights became negative in the regression analysis. The basic requirements were not met and consequently, additional regressions were done; eventually forming formula #2. Formula #2 showed stable values and plausible parameter weights. When compared to a workload measuring model of today, formula #2 showed better performance. Despite the small amount of data samples, we were able to prove a genuine relation between three, of each other independent, variables and the traffic complexity.

Abstract Twentieth century, citizen “revolts” against highway projects have influenced thinking about public transport (Toronto, Vancouver, New York), governance (Portland), and cycling (The Netherlands) to this day. Less is known about how these emerge in developing countries, and what they can tell us about citizens’ role in innovation to achieve more socially just, good and livable cities.  Using a complexity-based approach, this dissertation explores lessons from an anti-highway movement in Santiago, Chile (1997), which challenged authoritarian planning paradigms inherited from the Pinochet regime (1973-1990). In 2000, these leaders of diverse communities founded a citizen institution, Living City (Ciudad Viva), which today is a prize-winning, citizen-led planning institution.  Participation is recognized as important to community development, health and urban planning. Nonetheless, a rich literature notes many limitations. Is improving participation just a matter of “getting the process right”? Or does it require re-formulating frameworks to redistribute power, fostering self-generating civil society organizations, and treating democratization as ongoing rather than a “steady state”?  Re-formulating frameworks has far-reaching implications. It requires acting consistently with the premise that the local is central to change in human living systems, and the need to create the civic “infrastructure” conducive to citizen learning and the emergence of multiscalar citizen organizations, able to mobilize ecology of actors for innovation. To effectively address the challenges of climate change, loss of biodiversity, the social determinants of health, the “obesity epidemic” and other issues, the answers lie in city neighbourhoods and human settlements.  If we aspire to good, just and livable cities, uncertain futures require planning for change. This research suggests that we can identify dynamics likely to leverage significant change and activate capacities throughout a system. This requires moving to an inclusive planning paradigm that fully integrates citizen planners.

The present thesis is dedicated to two topics in Dynamics of Holomorphic maps. The first topic is dynamics of simple parabolic germs at the origin. The second topic is Polynomial-time Computability of Julia sets.\\ Dynamics of simple parabolic germs. Let $F$ be a germ with a simple parabolic fixed point at the origin: $F(w)=w+w^2+O(w^3).$ It is convenient to apply the change of coordinates $z=-1/w$ and consider the germ at infinity $$f(z)=-1/F(-1/z)=z+1+O(z^{-1}).$$ The dynamics of a germ $f$ can be described using Fatou coordinates. Fatou coordinates are analytic solutions of the equation $\phi(f(z))=\phi(z)+1.$ This equation has a formal solution \[\tilde\phi(z)=\text{const}+z+A\log z+\sum_{j=1}^\infty b_jz^{-j},\] where $\sum b_jz^{-j}$ is a divergent power series. Using \'Ecalle's Resurgence Theory we show that $\tilde$ can be interpreted as the asymptotic expansion of the Fatou coordinates at infinity. Moreover, the Fatou coordinates can be obtained from $\tilde \phi$ using Borel-Laplace summation. J.~\'Ecalle and S.~Voronin independently constructed a complete set of invariants of analytic conjugacy classes of germs with a parabolic fixed point. We give a new proof of validity of \'Ecalle's construction. \\ Computability of Julia sets. Informally, a compact subset of the complex plane is called \emph if it can be visualized on a computer screen with an arbitrarily high precision. One of the natural open questions of computational complexity of Julia sets is how large is the class of rational functions (in a sense of Lebesgue measure on the parameter space) whose Julia set can be computed in a polynomial time. The main result of Chapter II is the following: Theorem. Let $f$ be a rational function of degree $d\ge 2$. Assume that for each critical point $c\in J_f$ the $\omega$-limit set $\omega(c)$ does not contain either a critical point or a parabolic periodic point of $f$. Then the Julia set $J_f$ is computable in a polynomial time.

Abstract Twentieth century, citizen “revolts” against highway projects have influenced thinking about public transport (Toronto, Vancouver, New York), governance (Portland), and cycling (The Netherlands) to this day. Less is known about how these emerge in developing countries, and what they can tell us about citizens’ role in innovation to achieve more socially just, good and livable cities.  Using a complexity-based approach, this dissertation explores lessons from an anti-highway movement in Santiago, Chile (1997), which challenged authoritarian planning paradigms inherited from the Pinochet regime (1973-1990). In 2000, these leaders of diverse communities founded a citizen institution, Living City (Ciudad Viva), which today is a prize-winning, citizen-led planning institution.  Participation is recognized as important to community development, health and urban planning. Nonetheless, a rich literature notes many limitations. Is improving participation just a matter of “getting the process right”? Or does it require re-formulating frameworks to redistribute power, fostering self-generating civil society organizations, and treating democratization as ongoing rather than a “steady state”?  Re-formulating frameworks has far-reaching implications. It requires acting consistently with the premise that the local is central to change in human living systems, and the need to create the civic “infrastructure” conducive to citizen learning and the emergence of multiscalar citizen organizations, able to mobilize ecology of actors for innovation. To effectively address the challenges of climate change, loss of biodiversity, the social determinants of health, the “obesity epidemic” and other issues, the answers lie in city neighbourhoods and human settlements.  If we aspire to good, just and livable cities, uncertain futures require planning for change. This research suggests that we can identify dynamics likely to leverage significant change and activate capacities throughout a system. This requires moving to an inclusive planning paradigm that fully integrates citizen planners.

This thesis comprises of two separate game theoretic models that fall under the general umbrella of network formation games. The first is a coalitional model of interaction in social networks that is based on the idea of social distance, in which players seek interactions with similar others. Our model captures some of the phenomena observed on such networks, such as homophily driven interactions and the formation of small worlds for groups of players. Using social distance games, we analyze the interactions between players on the network, study the properties of efficient and stable networks, relate them to the underlying graphical structure of the game, and give an approximation algorithm for finding optimal social welfare. We then show that efficient networks are not necessarily stable, and stable networks do not necessarily maximise welfare. We use the stability gap to investigate the welfare of stable coalition structures, and propose two new solution concepts with improved welfare guarantees. The second model is a compact formulation of matchings with externalities. Our formulation achieves tractability of the representation at the expense of full expressivity. We formulate a template of solution concept that applies to games where externalities are involved, and instantiate it in the context of optimistic, neutral, and pessimistic reasoning. Then we investigate the complexity of the representation in the context of many-to-many and one-to-one matchings, and provide both computational hardness results and polynomial time algorithms where applicable.

Network analysis in GIS is often related to finding solutions to transportation problems. In a GIS the real world is represented by either one of two spatial models, vector-based, or raster-based. Prefering raster or vector GIS is more a question of choice than of accuracy. A raster-based GIS model shows a better fit, when the problem is concerned with finding a path across terrain which does not have predefined paths. The approach of this study is to translate the scenario into a &lsquo / least-cost path&rsquo / graph with an associated cost function on the raster-based GIS layer. Sometimes, computation of shortest paths between different locations on a raster-based GIS has to be done in real-time. Therefore, knowing which shortest path algorithm runs fastest on real networks is needed. In order to meet this requirement, Dijsktra&rsquo / s algorithm with priority queue implementation is selected, because it reduces the time complexity of Dijsktra&rsquo / s algorithm from O(V2 log V) to O(E log V ). The run-time results of Dijsktra&rsquo / s algorithm, Dijsktra&rsquo / s algorithm with priority queue implementation and ArcMap Spatial Analyst Tool are compared for a number of raster GIS layers which have different number of nodes. Dijsktra&rsquo / s algorithm with priority queue implementation and Spatial Analyst tool of ArcMap show a linear relationship between node numbers and time, whereas Dijsktra&rsquo / s algorithm represents a quadratic relationship. Hence, when the number of nodes and edges in graph is increased, the run-time performance of the Dijsktra&rsquo / s algorithm decreases rapidly.

Historically, the paradigm of similarity of protein sequences implying common structure, function and ancestry was generalized based on studies of globular domains. The implications of sequence similarity among non-globular protein segments have not been studied to the same extent; nevertheless, homology considerations are silently extended for them. This appears especially detrimental in the case of transmembrane helices (TMs) and signal peptides (SPs) where sequence similarity is necessarily a consequence of physical requirements rather than common ancestry. Since the matching of SPs/TMs creates the illusion of matching hydrophobic cores, the inclusion of SPs/TMs into domain models can give rise to wrong annotations. More than 1001 domains among the 10,340 models of Pfam release 23 and 18 domains of SMART version 6 (out of 809) contain SP/TM regions. As expected, fragment mode HMM searches generate promiscuous hits limited to solely the SP/TM part among clearly unrelated proteins. More worryingly, this work shows explicit examples that the scores of clearly false-positive hits, even in globalmode searches, can be elevated into the significance range just by matching the hydrophobic runs. In the PIR iProClass database v3.74 using conservative criteria, this study finds that at least between 2.1% and 13.6% of its annotated Pfam hits appear unjustified for a set of validated domain models. Thus, false positive domain hits enforced by SP/TM regions can lead to dramatic annotation errors where the hit has nothing in common with the problematic domain model except the SP/TM region itself. A workflow of flagging problematic hits arising from SP/TM-containing models for critical reconsideration by annotation users is provided. While E-value guided extrapolation of protein domain annotation from libraries such as Pfam with the HMMER suite is indispensable for hypothesizing about the function of experimentally uncharacterized protein sequences, it can also complicate the annotation problem. In HMMER2, the E-value is computed from the score via a logistic function or via a domain model-specific extreme value distribution (EVD); the lower of the two is returned as E-value for the domain hit in the query sequence. We demonstrated that, for thousands of domain models, this treatment results in switching from the EVD to the statistical model with the logistic function when scores grow (for Pfam release 23, 99% in the global mode and 75% in the fragment mode). If the score corresponding to the breakpoint results in an E-value above a user-defined threshold (e.g., 0.1), a critical score region with conflicting E-values from the logistic function (below the threshold) and from EVD (above the threshold) does exist. Thus, this switch will affect E-value guided annotation decisions in an automated mode. To emphasize, switching in the fragment mode is of no practical relevance since it occurs only at E-values far below 0.1. Unfortunately, a critical score region does exist for 185 domain models in the hmmpfam and 1748 domain models in the hmmsearch global-search mode. For 145 out the respective 185 models, the critical score region is indeed populated by actual sequences. In total, 24.4% of their hits have a logistic function-derived E-value<0.1 when the EVD provides an E-value>0.1. Examples of false annotations are provided and the appropriateness of a logistic function as alternative to the EVD is critically discussed. This work shows that misguided E-value computation coupled with non-globular regions embedded in domain model library not only causes annotation errors in public databases but also limits the extrapolation power of protein function prediction tasks. So far, the preceding work has demonstrated that sequence homology considerations widely used to transfer functional annotation to uncharacterized protein sequences require special precautions in the case of non-globular sequence segments including membrane-spanning stretches from non-polar residues. We found that there are two types of transmembrane helices (TMs) in membrane-associated proteins. On the one hand, there are so-called simple TMs with elevated hydrophobicity, low sequence complexity and extraordinary enrichment in long aliphatic residues. They merely serve as membrane-anchoring device. In contrast, so-called complex TMs have lower hydrophobicity, higher sequence complexity and some functional residues. These TMs have additional roles besides membrane anchoring such as intramembrane complex formation, ligand binding or a catalytic role. Simple and complex TMs can occur both in single- and multi-membrane-spanning proteins essentially in any type of topology. Whereas simple TMs have the potential to confuse searches for sequence homologues and to generate unrelated hits with seemingly convincing statistical significance, complex TMs contain essential evolutionary information. For extending the homologyconcept onto membrane proteins, we provide a necessary quantitative criterion to distinguish simple TMs in query sequences prior to their usage in homology searches based on assessment of hydrophobicity and sequence complexity of the TM sequence segments. Theoretical insights from this work were applied to problems of function prediction for specific uncharacterized gene/protein sequences (for example, APMAP and ARXES) and for the functional classification of TM-containing proteins.

In this workshop we present an innovative teaching, learning and research setting that engages beginning teachers in mathematical inquiry as they investigate, represent and connect mathematical ideas through mathematical conversation, reasoning and argument. This workshop connects to the themes of teacher preparation and teaching through problem solving. Drawing on new paradigms to think about teaching and learning, we orient our work within complexity theory (Davis & Sumara, 2006; Holland, 1998; Johnson, 2001; Maturana & Varela, 1987; Varela, Thompson & Rosch, 1991) to understand teaching|learning as a complex iterative process through which opportunities for learning arise out of dynamic interactions. Varela, Thompson and Rosch, (1991) use the term co-emergence to understand how the individual and the environment inform each other and are “bound together in reciprocal specification and selection” (p.174). In particular we are interested in the conditions that enable the co-emergence of teaching|learning collectives that support the generation of new mathematical and pedagogical ideas and understandings. The setting is a one-week summer math program designed for prospective elementary teachers to deepen particular mathematical concepts taught in elementary school. The program is facilitated by recently graduated secondary mathematics teachers to provide them an opportunity to experience mathematics teaching|learning through rich problems. The data collected include questionnaires, interviews, and video recordings. Our analyses show that many a-ha moments of mathematical and pedagogical insight are experienced by both groups as they work together throughout the week. In this workshop we will actively engage the audience in an exploration of the mathematics problems that we pose in this unique teaching|learning environment. We will present our data on the participants’ mathematical and pedagogical responses and open a discussion of the implications of our work.

The importance of family involvement is highlighted by findings that parents’ behaviours, beliefs and attitudes affect children’s behaviour in a major way. The Family Maths programme, which is the focus of this study, provides support for the transformative education practices targeted by the South African Department of Education by offering an intervention which includes teachers, learners and their families in an affirming learning community. In this study participating parents were interviewed to investigate their perceptions of the Family Maths programme mainly in terms of their engagement, enjoyment and confidence levels. The major themes and ideas that were generated in this study include the development of positive attitudes, parents and children working and talking together, and the skills exhibited by Family Maths facilitators. These findings are analysed within the parameters of complexity science and the pre-requisite conditions for developing a complex learning community, viz. internal diversity, redundancy, decentralized control, organised randomness and neighbour interactions.