Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop Parameterized complexity became over last two decades one of the most impor- tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc- tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the tree-depth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the tree-width of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...

We investigate F-Borel topological spaces. We focus on finding out how a complexity of a space depends on where the space is embedded. Of a particular interest is the problem of determining whether a complexity of given space X is absolute (that is, the same in every compactification of X). We show that the complexity of metrizable spaces is absolute and provide a sufficient condition for a topological space to be absolutely Fσδ. We then investigate the relation between local and global complexity. To improve our understanding of F-Borel spaces, we introduce different ways of representing an F-Borel set. We use these tools to construct a hierarchy of F-Borel spaces with non-absolute complexity, and to prove several other results. 1

Research has shown that children with language impairment (LI) exhibit difficulties with both social communication and syntax. This study analyzed the effect of a social communication intervention on syntactic development, focusing on grammatical complexity in three children with LI when enacting stories. The intervention included reading and enacting stories, playing games with picture emotion cards and journaling. Each child's mean length of terminal unit (t-unit), the number and type of subordinate clauses they produced per t-unit, and the grammaticality of their complex sentences was analyzed. While none of the children increased their mean length of t-unit or the grammaticality of their sentences, one participant showed a slight increase in the number of subordinate clauses she used and another participant changed the basic format with which she enacted stories to a more mature format. The results of this study did not support the claim that a single intervention could target both social communicative and syntactic goals simultaneously. There were limitations to this study that, if addressed, could potentially support this claim.

Engineering complex systems and New Product Development (NPD) are major challenges for contemporary engineering design and must be studied at three levels of: Products, Processes and Organizations (PPO). The science of complexity indicates that complex systems share a common characteristic: they are robust yet fragile. Complex and large scale systems are robust in the face of many uncertainties and variations; however, they can collapse, when facing certain conditions. This is so since complex systems embody many subtle, intricate and nonlinear interactions. If formal modelling exercises with available computational approaches are not able to assist designers to arrive at accurate predictions, then how can we immunize our large scale and complex systems against sudden catastrophic collapse? This thesis is an investigation into complex product design. We tackle the issue first by introducing a template and/or design methodology for complex product design. This template is an integrated product design scheme which embodies and combines elements of both design theory and organization theory; in particular distributed (spatial and temporal) problem solving and adaptive team formation are brought together. This design methodology harnesses emergence and innovation through the incorporation of massive amount of numerical simulations which determines the problem structure as well as the solution space characteristics. Within the context of this design methodology three design methods based on measures of complexity are presented. Complexity measures generally reflect holistic structural characteristics of systems. At the levels of PPO, correspondingly, the Immunity Index (global modal robustness) as an objective function for solutions, the real complexity of decompositions, and the cognitive complexity of a design system are introduced These three measures are helpful in immunizing the complex PPO from chaos and catastrophic failure. In the end, a conceptual decision support system (DSS) for complex NPD based on the presented design template and the complexity measures is introduced. This support system (IMMUNE) is represented by a Multi Agent Blackboard System, and has the dual characteristic of the distributed problem solving environments and yet reflecting the centralized viewpoint to process monitoring. In other words IMMUNE advocates autonomous problem solving (design) agents that is the necessary attribute of innovative design organizations and/or innovation networks; and at the same time it promotes coherence in the design system that is usually seen in centralized systems.

Despite a general recognition of the importance of complex systems, there is a dearth of general models capable of describing their dynamics. This is attributed to a complexity scale; the models are attempting to describe systems at different parts of the scale and are hence not compatible. We require new models capable of describing complex behaviour at different points of the complexity scale. This work identifies, and proceeds to examine systems at the high end of the complexity scale, those which have not to date been well understood by our current modelling methodology. It is shown that many such models exhibit what might be termed contextual dependency, and that it is precisely this feature which is not well understood by our current modelling methodology. A particular problem is discussed; our apparent inability to generate systems which display high end complexity, exhibited by for example the general failure of strong ALife. A new model, Process Physics, that has been developed at Flinders University is discussed, and arguments are presented that it exhibits high end complexity. The features of this model that lead to its displaying such behaviour are discussed, and the generalisation of this model to a broader range of complex systems is attempted.

<p>There is a common belief amongst those who are involved in projects that as project complexity increases the difficulty to manage a project increases and thus the probability to succeed in project completion considerably decreases. Perception of complexity in a project usually refers to common criteria from traditional project management thinking such as the scale of the project; cost; duration; and the degree of risk to its owner. However, whether a project is perceived to be complex or not may not be purely a product of the size of the project. It may also be derived from the person’s experience in projects. The aim of this study is to identify attributes of perception of project complexity and observe whether experience is also a determining factor in perceiving a project as complex. The research is based on the assumption that a complex project may exhibit behaviour similar to complex adaptive system. This study proposes a theoretical framework based on projects understood as complex adaptive systems. A project experience matrix is developed which will be useful to help link degree and type of experience to perceptions of project complexity.</p><p>This study employs a comparative study between two cases to explore and compare the perception of complexity in each case. Qualitative and quantitative data were obtained through semi-structured interview and questionnaires, then analysed accordingly. The outcomes of this research attempted to find answers to the following questions: How do project managers and team members perceive a project as complex (project complexity)?” In answering this question we explored how project managers and team members perceived project complexity. The major question above was elaborated by some minor specific questions. These are: Which attributes of complex adaptive systems are attributed by project managers and team members to project complexity? Is project experience a determining factor to the perception of project complexity? Based on our sample we found no significant differences between attributes of complex adaptive systems and perception of project complexity; no significant association between depth and context of experience and perception of project complexity. We also found no significant differences between the Chinese and Indonesian samples.</p>

The aim of this study is to test the audit fee determinants for companies listed on Nasdaq OMX Stockholm Stock Exchange and to examine whether the audit fee determinants diverge for ownership structures. By testing the audit fee determinants in a Swedish setting the study contributes to the research body in two ways; by testing a previously sparsely researched setting and examining the monitoring need for different ownership structures. The results indicate that audit fees are explained to a large extent by accounting complexities, business complexities and assurance.  The results also suggest that ownership structure does not have a large effect on the monitoring need.  Altogether the results provide further evidence on audit fee determinants whilst adding initial insight into the area of audit fee determinants for ownership structures.

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer to this as a proof complexity resource problem, and provide comprehensive results for several forms of Resolution as well as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as practical motivations: Proof complexity research has focused on the size of proofs, and Resolution space requirements are an interesting new theoretical area of study. In more practical terms, the Resolution proof system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we investigate and formalize what it means for a reduction to be `dangerous'. The area of SAT-solving necessarily employs reductions in order to translate from other domains to SAT, where the power of highly-optimized algorithms can be brought to bear. Researchers have empirically observed that it is unfortunately possible for reductions to map easy instances from the input domain to hard SAT instances. We develop a non-Hamiltonicity proof system and combine it with additional results concerning the Prover/Delayer game from the first part of this thesis as well as proof complexity results for intuitionistic logic in order to provide the first formal examples of harmful and beneficial reductions, ultimately leading to the development of a framework for studying and comparing translations from one language to another.

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer to this as a proof complexity resource problem, and provide comprehensive results for several forms of Resolution as well as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as practical motivations: Proof complexity research has focused on the size of proofs, and Resolution space requirements are an interesting new theoretical area of study. In more practical terms, the Resolution proof system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we investigate and formalize what it means for a reduction to be `dangerous'. The area of SAT-solving necessarily employs reductions in order to translate from other domains to SAT, where the power of highly-optimized algorithms can be brought to bear. Researchers have empirically observed that it is unfortunately possible for reductions to map easy instances from the input domain to hard SAT instances. We develop a non-Hamiltonicity proof system and combine it with additional results concerning the Prover/Delayer game from the first part of this thesis as well as proof complexity results for intuitionistic logic in order to provide the first formal examples of harmful and beneficial reductions, ultimately leading to the development of a framework for studying and comparing translations from one language to another.

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We study the syntactic complexity of suffix-, bifix-, and factor-free regular languages, star-free languages including three subclasses, and R- and J-trivial regular languages. We found upper bounds on the syntactic complexities of these classes of languages. For R- and J-trivial regular languages, the upper bounds are n! and ⌊e(n-1)!⌋, respectively, and they are tight for n >= 1. Let C^n_k be the binomial coefficient ``n choose k''. For monotonic languages, the tight upper bound is C^{2n-1}_n. We also found tight upper bounds for partially monotonic and nearly monotonic languages. For the other classes of languages, we found tight upper bounds for languages with small state complexities, and we exhibited languages with maximal known syntactic complexities. We conjecture these lower bounds to be tight upper bounds for these languages. We also observed that, for some subclasses C of regular languages, the upper bound on state complexity of the reversal operation on languages in C can be met by languages in C with maximal syntactic complexity. For R- and J-trivial regular languages, we also determined tight upper bounds on the state complexity of the reversal operation.