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.

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. 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.

In the context of a growing social complexification, projects have evolved in the pastdecades from simple endeavours to complex and uncertain undertakings. Consequently,project complexity has emerged as an important research direction, and recently severalproject complexity frameworks have been suggested. However, little research has beendone in this area and there has been no study on the relationship of project complexity,in its holistic sense, and the risk of delay. Therefore, the study investigates the intricaterelationship between project complexity and project delay. The research is conducted inthe context of Enterprise Resource Planning system (ERP) implementation projects,which are inherently complex and often record delays. The study has a qualitative nature and adopts an inductive approach. Nine ERPimplementationprojects have been studied in order to answer the research question.Several sources of evidence (semi-structured interviews and questionnaires) have beenutilized to ensure the credibility of the research findings through triangulation. The study contributes to the research field by verifying and augmenting the existingframeworks on reasons for project delay, complexity categories and their interplay. Itwas identified that complexity in a holistic sense represents a necessary condition forproject delay. Moreover, the study showed that although ERP projects are oftenconsidered to be technically complex, their complexity stems mainly from ‘subjective’(or perceived) and ‘uncertainty’ complexity dimensions. Finally, the conceptual modelof Eden et al. (2005) was modified to reflect the findings of the study.

A measurement framework is presented for component oriented (CO) software systems. Fundamental concepts in component orientation are defined. The factors that influence CO systems&rsquo / structural complexity are identified. Metrics quantifying and characterizing these factors are defined. A set of properties that a CO complexity metric must satisfy are defined. Metrics are evaluated first using the set of properties defined in this thesis and also using the set of properties defined by Tian and Zelkowitz in [84]. Evaluation results revealed that metrics satisfy all properties in both sets. Empirical validation of metrics is performed using data collected from graduate students&rsquo / projects. Validation results revealed that CO complexity metrics can be used as predictors of development effort, Design effort, integration effort (characterizing system integrabiltiy), correction effort (characterizing system maintainability), function points count (characterizing system functionality), and programmer productivity. An Automated metrics collection tool is implemented and integrated with a dedicated CO modeling tool. The metrics collection tool automatically collects complexity metrics from system models and performs prediction estimations accordingly.

This dissertation examines the nexus of complexity theory and peace education and its implications for developing educational praxis that engages with the demands of global complexity. In this thesis, I argue that as societies become more globalized and complex (global complexity) there is an onus upon education to adapt its methods so people can understand the workings of these processes better and further develop the ethical and creative resources needed for responding to system dynamics effectively. My central thesis is that the most appropriate way to do this is to use methods that are congruent with the subject matter of global complexity - that is to align one's pedagogy with one's subject area. This dissertation therefore investigates the situated and contingent responses of peace educators working in the field to the challenges and opportunities that arise when attempting to adapt to local/global dynamics. It utilizes ethnography, narrative inquiry, and autoethnography and draws its data from interviews with over 50 educators in India, Japan, and the US. This research demonstrates that when engaging with global complexity, peace educators adapt both their ontological understanding and methodological orientation in ways congruent at times with the insights of complexity theory. While this understanding can be at odds with mass educational methodologies, this tension also is a touchstone for peace educator's creative formulation of novel praxis in response to the demands of global complexity. This dissertation thus examines some of the possibilities for learning within complex knowledge production systems and highlights the need for further research into the dynamics and processes at play within global educational 'networks'.

The thesis applies the ICC tecniques to the probabilistic polinomial complexity classes in order to get an implicit characterization of them. The main contribution lays on the implicit characterization of PP (which stands for Probabilistic Polynomial Time) class, showing a syntactical characterisation of PP and a static complexity analyser able to recognise if an imperative program computes in Probabilistic Polynomial Time. The thesis is divided in two parts. The first part focuses on solving the problem by creating a prototype of functional language (a probabilistic variation of lambda calculus with bounded recursion) that is sound and complete respect to Probabilistic Prolynomial Time. The second part, instead, reverses the problem and develops a feasible way to verify if a program, written with a prototype of imperative programming language, is running in Probabilistic polynomial time or not. This thesis would characterise itself as one of the first step for Implicit Computational Complexity over probabilistic classes. There are still open hard problem to investigate and try to solve. There are a lot of theoretical aspects strongly connected with these topics and I expect that in the future there will be wide attention to ICC and probabilistic classes.

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.

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.

The nature and function of Task Complexity, in the context of senior secondary mathematics, has been identified through: a search of the research literature; interviews with experts that focused on the nature of task complexity; expert use of the Williams/Clarke Framework of Complexity (1997) as a tool to categorise the complexity of a task, and observation and analysis of the responses of senior secondary mathematics students as they worked in collaborative groups to solve an unfamiliar challenging problem. Although frequently used in the literature to describe tasks, ‘complexity’ has often lacked definition. Expert opinion about the nature of mathematical complexity was ascertained by seeking the opinions of experts in the areas of mathematics, mathematics education, and gifted education. Expert opinion about task complexity was stimulated by questions about the relative complexity of two tasks. The experts then categorised the complexities within each of these tasks using the Williams/Clarke Framework of Complexity. This framework identifies the dimensions of task complexity and was found by experts to be both useful and adequate for this purpose. A theoretical framework was developed to assess student ability to solve challenging problems. This theoretical framework was used to design a test to assess student ability to solve challenging problems. The information this test provided about the problem solving ability of the students in this study informed my analysis of student response to complexity.

ROCHA, Thiago Alves. Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes ⊕P e NP∩coNP através de lógicas com quantificadores de segunda ordem. 2014. 81 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:02:32Z No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:36:28Z (GMT) No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) / Made available in DSpace on 2016-07-22T12:36:28Z (GMT). No. of bitstreams: 1 2014_dis_tarocha.pdf: 600184 bytes, checksum: 8e317715dd15118a1061361a5251f08e (MD5) Previous issue date: 2014 / Many computable problems can be solved more efficiently or in a more natural way through probabilistic algorithms, which shows that the use of such algorithms is quite relevant in Computer Science. However, probabilistic algorithms may return a wrong answer with a certain probability. Also, the use of probabilistic algorithms does not solve problems that are not computable. In Computational Complexity, the complexity of a problem is characterized based on the amount of computational resources, such as space and time, needed to solve it. Problems that have the same complexity compose the same class. The computational complexity classes are related by a hierarchy. In Descriptive Complexity, a logic is used to express problems and capture computational complexity classes in order to express all and only the problems of this class. Thus, the complexity of a problem does not depend on physical factors, such as time and space, but only on the expressiveness of the logic that defines it. Important results of the area states that several classes of computational complexity can be characterized by a logic. For example, the class NP has been shown equivalent to the class of problems expressed by the existential fragment of Second-Order Logic. This close relationship between these areas allows some results about Logics to be transferred to Computational Complexity and vice versa. Despite of the importance of probabilistic algorithms and of Descriptive Complexity, there are few results on the characterization, by a logic, of probabilistic computational complexity classes. In this work, we show characterizations for each of the polinomial time probabilistic complexity classes. In our results, we use second-order generalized quantifiers to simulate the acceptance of the nondeterministic machines of these classes. We found Logical characterizations in the literature only for classes PP and BPP. In the first case, the logic employed was the first-order added by a quantifier most of second-order. With the approach established in this work, we obtain an alternative proof for the characterization of PP. With the same methodology, we also characterize the class ⊕P through a logic with a second-order parity quantifier. In the case of BPP , there was a result that used a logic with probabilistic semantics. Using our approach of generalized quantifiers, we obtain an alternative characterization for this class. With the same method, we were able to characterize the probabilistic semantic classes RP, coRP, ZPP and the semantic class NP ∩ coNP. Finally, we show an application of Descriptive Complexity results in the creation of algorithms from a logic specification. / Vários problemas computáveis podem ser resolvidos de maneira mais eficiente ou mais natural através de algoritmos probabilísticos, o que mostra que o uso de tais algoritmos é bastante relevante em computação. Entretanto, os algoritmos probabilísticos podem retornar uma resposta errada com uma certa probabilidade. Observe, ainda que o uso de algoritmos probabilísticos não resolve problemas não computáveis. A Complexidade Computacional caracteriza a complexidade de um problema a partir da quantidade de recursos computacionais, como espaço e tempo, para resolvê-lo. Problemas que tem a mesma complexidade compõem uma classe. As classes de complexidade computacional são relacionadas através de uma hierarquia. A Complexidade Descritiva usa lógicas para expressar os problemas e capturar classes de complexidade computacional no sentido de expressar todos, e apenas, os problemas desta classe. Dessa forma, a complexidade de um problema não depende de fatores físicos, como tempo e espaço, mas apenas da expressividade da lógica que o define. Resultados importantes da área mostraram que várias classes de complexidade computacional podem ser caracterizadas por lógicas. Por exemplo, a classe NP foi mostrada equivalente à classe dos problemas expressos pelo fragmento existencial da Lógica de Segunda Ordem. Este estreito relacionamento entre tais áreas permite que alguns resultados da área de Lógica sejam transferidos para a de Complexidade Computacional e vice-versa. Apesar da importância de algoritmos probabilísticos e da Complexidade Descritiva, existem poucos resultados de caracterização, por lógicas, das classes de complexidade computacional probabilísticas. Neste trabalho, buscamos mostrar caracterizações para cada uma das classes de complexidade probabilísticas de tempo polinomial. Nos nossos resultados, utilizamos quantificadores generalizados de segunda ordem para simular a aceitação das máquinas não-determinísticas dessas classes. Achamos caracterizações lógicas na literatura apenas para as classes PP e BPP. No primeiro caso, a lógica utilizada era a de primeira ordem adicionada de um quantificador maioria de segunda ordem. Com a abordagem criada neste trabalho, conseguimos obter uma prova alternativa para a caracterização de PP. Com essa mesma metodologia, também conseguimos caracterizar a classe ⊕P através de uma lógica com um quantificador de paridade. No caso de BPP, existia um resultado que utilizava uma lógica com semântica probabilística. Usando nossa abordagem de quantificadores generalizados, conseguimos obter uma caracterização alternativa para essa classe. Com o mesmo método, conseguimos caracterizar as classes probabilísticas semânticas RP, coRP, ZPP e a classe semântica NP∩coNP. Por fim, mostramos uma aplicação dos resultados de Complexidade Descritiva na criação de algoritmos através de uma especificação lógica.