This thesis expands on the notion of linear complexity for a graph as defined by Michael Orrison and David Neel in their paper "The Linear Complexity of a Graph." It considers additional classes of graphs and provides upper bounds for additional types of graphs and graph operations.

For many applications, such as cryptography and digital communications, binary sequences with certain specific properties are required. These include a balance of 0's and 1's in a period, ideal runs frequencies, good auto- and cross-correlation spectra, and high linear complexity. Perfect Linear Complexity Profile sequences (PLCPs) have the linear complexity of all subsequences (starting with the first bit) equal to half the length of the subsequence (this is the expected value for a random sequence). We investigate the density - proportion of ones - of finite length PLCPs, both in general and for specific examples. We gain results on the average, maximal and minimal densities, as well as their limits as the length tends to infinity. We also study whether the PLCP property is preserved under various decimations. PLCPs are characterised by a simple linear recurrence modulo 2. We look at similar "nearly" perfect profiles and characterise sequences with these profiles in terms of similar recurrences. Also sequences with a PLCP up to a point and then constant complexity are characterised in terms of the convergents in the continued fraction expansion of the generating function of PLCPs, and we look briefly at their corresponding periods. Sequences with bounded jumps in their linear complexity are discussed and a method of generating them is suggested. The interleaving of shifts of a sequence with out-of-phase auto-correlation equal to -1 and balance, in a specific order, seems to be a fundamental method of generating longer sequences with this auto-correlation property. It is shown that two pairs of families of these sequences, derived in different ways, are in fact equivalent. The analysis highlights the general method mentioned above, and so provides examples of families of sequences with 2-valued auto-correlation by changing the ingredients in the interleaving pattern. We also look at the cross-correlation of sequences with this interleaved structure.

Generating functions are important tools that are used in many areas of mathematics and especially statistics. Besides analyzing the general structure of sequences and their asymptotic behavior / these functions, which can be roughly thought as the transformation of sequences into functions, are also used effciently to solve combinatorial problems. In this thesis, the effects of the transformations of generating functions on their corresponding sequences and the effects of the change in sequences on the generating functions are examined. With these knowledge, the generating functions for the resulting sequence of some combinatorial problems such as number of partitions, number of involutions, Fibonacci numbers and Catalan numbers are found. Moreover, some mathematical identities are proved by using generating functions. The sequences are the bases of especially symmetric key cryptosystems in cryptography. It is seen that by using generating functions, linear complexities and periods of sequences generated by constant coeffcient linear homogeneous recursions, which are used in linear feedback shift register (LFSR) based stream ciphers, can be calculated. Hence studying generating functions leads to have a better understanding in them. Therefore, besides combinatorial problems, such recursions are also examined and the results are used to observe the linear complexity and the period of LFSR&rsquo / s combined in different ways to generate &ldquo / better&rdquo / system of stream cipher.

Pseudorandom sequences have many applications in fields such as wireless communication, cryptography and built-in self test of integrated circuits. Maximal length sequences (m-sequences) are commonly employed pseudorandom sequences because they have ideal randomness properties like balance, run and autocorrelation. However, the linear complexity of m-sequences is poor. This thesis considers the use of one-dimensional Cellular Automata (CA) to generate pseudorandom sequences that have high linear complexity and good randomness. The properties of these sequences are compared with those of the corresponding m-sequences to determine their suitability. / Graduate

In cryptography, periodic sequences with terms in F2 are used almost everywhere. These sequences should have large linear complexity to be cryptographically strong. In fact, the linear complexity of a sequence should be close to its period. In this thesis, we study the expected value for N-periodic sequences with terms in the finite field Fq. This study is entirely devoted to W. Meidl and Harald Niederreiter&rsquo / s paper which is &ldquo / On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences&rdquo / We only expand this paper, there is no improvement. In this paper there are important theorems and results about the expected value of linear complexity of periodic sequences.

abstract: The main objective of this research is to develop an integrated method to study emergent behavior and consequences of evolution and adaptation in engineered complex adaptive systems (ECASs). A multi-layer conceptual framework and modeling approach including behavioral and structural aspects is provided to describe the structure of a class of engineered complex systems and predict their future adaptive patterns. The approach allows the examination of complexity in the structure and the behavior of components as a result of their connections and in relation to their environment. This research describes and uses the major differences of natural complex adaptive systems (CASs) with artificial/engineered CASs to build a framework and platform for ECAS. While this framework focuses on the critical factors of an engineered system, it also enables one to synthetically employ engineering and mathematical models to analyze and measure complexity in such systems. In this way concepts of complex systems science are adapted to management science and system of systems engineering. In particular an integrated consumer-based optimization and agent-based modeling (ABM) platform is presented that enables managers to predict and partially control patterns of behaviors in ECASs. Demonstrated on the U.S. electricity markets, ABM is integrated with normative and subjective decision behavior recommended by the U.S. Department of Energy (DOE) and Federal Energy Regulatory Commission (FERC). The approach integrates social networks, social science, complexity theory, and diffusion theory. Furthermore, it has unique and significant contribution in exploring and representing concrete managerial insights for ECASs and offering new optimized actions and modeling paradigms in agent-based simulation. / Dissertation/Thesis / Ph.D. Industrial Engineering 2013