In this thesis, we cover the general topic of state complexity. In particular, we examine the bounds on the state complexity of some different representations of regular languages. As well, we consider the state complexity of the operation root(<i>L</i>). We give quick treatment of the deterministic state complexity bounds for nondeterministic finite automata and regular expressions. This includes an improvement on the worst-case lower bound for a regular expression, relative to its alphabetic length. The focus of this thesis is the study of the increase in state complexity of a regular language <i>L</i> under the operation root(<i>L</i>). This operation requires us to examine the connections between abstract algebra and formal languages. We present results, some original to this thesis, concerning the size of the largest monoid generated by two elements. Also, we give good bounds on the worst-case state complexity of root(<i>L</i>). In turn, these new results concerning root(<i>L</i>) allow us to improve previous bounds given for the state complexity of two-way deterministic finite automata.

Combinatorial auctions (CAs) are an important mechanism for allocating multiple items while allowing agents to specify preferences over bundles of items. In order to communicate these preferences, agents submit bids, which consist of one or more items and a value indicating the agent’s preference for these items. The process of determining the allocation of items is known as the winner determination problem (WDP). WDP for CAs is known to be NP-complete in the general case. We consider two distinct graph representations of a CA; the bid graph and the item graph. In a bid graph, vertices represent bids, and two vertices are adjacent if and only if the bids share items in common. In an item graph, each vertex represents a unique item, there is a vertex for each item, and any bid submitted by any agent must induce a connected subgraph of the item graph. We introduce a new definition of combinatorial auction equivalence by declaring two CAs equivalent if and only if their bid graphs are isomorphic. Parameterized complexity theory can be used to further distinguish between NP-hard problems. In order to make use of parameterized complexity theory in the investigation of a problem, we aim to find one or more parameters that describe some aspect of the problem such that if we fix these parameters, then either the problem is still hard (fixed-parameter intractable), or the problem can be solved in polynomial time (fixed-parameter tractable). We analyze WDP using bid graphs from within the formal scope of parameterized complexity theory. This approach has not previously been used to analyze WDP for CAs, although it has been used to solve set packing, which is related to WDP for CAs and is discussed in detail. We investigate a few parameterizations of WDP; some of the parameterizations are shown to be fixed-parameter intractable, while others are fixed-parameter tractable. We also analyze WDP when the graph class of a bid graph is restricted. We also discuss relationships between item graphs and bid graphs. Although both graphs can represent the same problem, there is little previous work analyzing direct relationships between them. Our discussion on these relationships begins with a result by Conitzer et al. [7], which focuses on the item graph representation and its treewidth, a property of a graph that measures how close the graph is to a tree. From a result by Gavril, if an item graph has treewidth one, then the bid graph must be chordal [16]. To apply the other direction of Gavril’s theorem, we use our new definition of CA equivalence. With this new definition, Gavril’s result shows that if a bid graph of a CA is chordal, then we can construct an item graph that has treewidth one for some equivalent CA.

We consider the problem of finding a sparse multiple of a polynomial. Given a polynomial f ∈ F[x] of degree d over a field F, and a desired sparsity t = O(1), our goal is to determine if there exists a multiple h ∈ F[x] of f such that h has at most t non-zero terms, and if so, to find such an h. When F = Q, we give a polynomial-time algorithm in d and the size of coefficients in h. For finding binomial multiples we prove a polynomial bound on the degree of the least degree binomial multiple independent of coefficient size. When F is a finite field, we show that the problem is at least as hard as determining the multiplicative order of elements in an extension field of F (a problem thought to have complexity similar to that of factoring integers), and this lower bound is tight when t = 2.

In this thesis, motivated by modelling polymers, the topological entanglement complexity of systems of two self-avoiding polygons (2SAPs), stretched polygons and systems of self-avoiding walks (SSAWs) in a tubular sublattice of Z3 are investigated. In particular, knotting and linking probabilities are used to measure a polygonfs selfentanglement and its entanglement with other polygons respectively. For the case of 2SAPs, it is established that the homological linking probability goes to one at least as fast as 1-O(n^(-1/2)) and that the topological linking probability goes to one exponentially rapidly as n, the size of the 2SAP, goes to infinity. For the case of stretched polygons, used to model ring polymers under the influence of an external force f, it is shown that, no matter the strength or direction of the external force, the knotting probability goes to one exponentially as n, the size of the polygon, goes to infinity. Associating a two-component link to each stretched polygon, it is also proved that the topological linking probability goes to unity exponentially fast as n&rightarrow;&infin;. Furthermore, a set of entangled chains confined to a tube is modelled by a system of self- and mutually avoiding walks (SSAW). It is shown that there exists a positive number &gamma; such that the probability that an SSAW of size n has entanglement complexity (EC), as defined in this thesis, greater than &gamma;n approaches one exponentially as n&rightarrow;&infin;. It is also established that EC of an SSAW is bounded above by a linear function of its size. Using a transfer-matrix approach, the asymptotic form of the free energy for the SSAW model is also obtained and the average edge-density for span m SSAWs is proved to approach a constant as m&rightarrow;&infin;. Hence, it is shown that EC is a ggoodh measure of entanglement complexity for dense polymer systems modelled by SSAWs, in particular, because EC increases linearly with system size, as the size of the system goes to infinity.

<p>Background: Each year, 2 million older Americans complete three to four week courses of post-acute care in nursing homes and return home; however, scant research describes services to protect older adults during their transitions from nursing homes to home. In hospital-based studies, transitional care interventions were associated with improved health outcomes for older adults, but these interventions added new staff positions, which are likely cost-prohibitive in nursing homes. Further, no prior study explored transitional care provided for vulnerable, post-acute care patients in nursing homes. Thus, this dissertation was designed to develop new understandings about transitional care provided by existing staff members in nursing homes. The study has two specific aims: (a) describe transitional care and outcomes for older adults who obtain post-acute care in nursing homes from the day of admission through discharge; (b) explore the influence of interactions, among selected older adult patients and their group of nursing home caregivers, on their ability to accomplish transitional care processes.</p><p>Method: Using data from a literature review and theoretical models, including Donabedian's Model of Healthcare Quality and Anderson's Local Interaction Model, a conceptual model of transitional care for post-acute care patients in nursing homes was constructed. The conceptual model was then used to guide exploration of the research aims with a longitudinal, multiple case study of transitional care in a nursing home. The unit of analysis was the patient care-team, defined as individual post-acute care patients, family caregivers, and 6 to 8 professional staff in each team (e.g., rehabilitation therapists, physicians, nurses and social workers). Three patient care-team members were purposively sampled for study. Moreover, longitudinal data were collected using repeated interviews and observations with patients, family caregivers, and staff; document and daily chart reviews; and surveys of patient preparedness for discharge. Manifest content analysis and thematic analysis (qualitative methods) were used to conduct within- and across-case analyses of trajectories of transitional care and to identify strengths, gaps and inconsistencies in care. </p><p>Results: Findings related to the first research aim include a description of transitional care in the study nursing home. Serious gaps and inconsistencies in transitional care exposed older, post-acute care patients to risks for complications in their transitions from the study nursing home to home: (a) systemic supports were not available to support nursing home staff who provided transitional care; further, nursing home staff and leadership were unaware that they provided transitional care; (b) care processes were not in place to prepare older adults and their caregivers to continue care at home; (c) care-team interactions often excluded family members; and (d) post-acute care patients left the nursing home without resources needed to support safe transitions in care, including transitional care plans, education to appropriately respond to acute changes in health, written materials to guide care at home, referrals for medical follow-up after discharge, and transfers of clinical information to primary care physicians. </p><p>Findings related to the second research aim include a description of local interaction strategies and the effectiveness of transitional care processes. When professional staff more consistently used local interaction strategies, specified in the model, care-team members exhibited greater capacity for connections, information exchange, and cognitive diversity. Further, when care-team interactions were of high quality and sufficient frequency, there were multiple indications of more effective transitional care, such as patient engagement in care, inclusion of patient priorities in care plans, and problem solving which included family members and diverse members of the patient care-team. Thus, local interaction strategies were essential staff behaviors needed to adapt care processes to the specific transitional care needs of individual patients.</p><p>Because transitional care is a grossly under-developed care process in nursing homes, these findings will likely have immediate implications for practice and research. Findings will provide nursing home administrators and staff with resources to develop and evaluate care in nursing homes; further, the findings will help to create targets for protocol and care process development to strengthen existing practice and address deficiencies. Findings will provide researchers with resources for studying transitional care in diverse samples of nursing homes, which should facilitate development of testable hypotheses for needed intervention studies. In addition, the local interaction strategies findings in the study may generalize to other settings of care, where interdependent staff work is required to establish connections, information networks, and to coordinate care among multiple staff members.</p> / Dissertation

<p>For at least two thousand years, voting has been used as one of the most effective ways to aggregate people's ordinal preferences. In the last 50 years, the rapid development of Computer Science has revolutionize every aspect of the world, including voting. This motivates us to study (1) <bold>conceptually, how computational thinking changes the traditional voting theory</bold>, and (2) <bold>methodologically, how to better use voting for preference/information aggregation with the help of Computer</p><p>Science</bold>.</p><p>My Ph.D. work seeks to investigate and foster the interplay between Computer Science and Voting Theory. In this thesis, I will discuss two specific research directions pursued in my Ph.D. work, one for each question asked above. The first focuses on investigating how computational thinking affects the game-theoretic aspects of voting. More precisely, I will discuss the rationale and possibility of using computational complexity to protect voting from a type of strategic behavior of the voters, called <italic>manipulation</italic>. The second studies a voting setting called <italic>Combinatorial Voting</italic>, where the set of alternative is exponentially large and has a combinatorial structure. I will focus on the design and analysis of novel voting rules for combinatorial voting that balance computational efficiency and the expressivity of the voting language, in light of some recent developments in Artificial Intelligence.</p> / Dissertation

In the last twenty years, algebraic techniques have been applied with great success to several areas in theoretical computer science. However, for many problems involving modular counting, there is a huge gap in our understanding depending on whether the modulus is prime or composite. A prime example is the problem of showing lower bounds for circuits with Mod gates in circuit complexity. Proof techniques that work well for primes break down over composites. Moreover, in some cases, the problem for composites turns out to be very different from the prime case. Making progress on these problems seems to require a better understanding of polynomials over composites. In this thesis, we address some such "prime vs. composite" problems from algorithms, complexity and combinatorics, and the surprising connections between them. We consider the complexity-theoretic problem of computing Boolean functions using polynomials modulo composites. We show that symmetric polynomials can viewed as simultaneous communication protocols. This equivalence allows us to use techniques from communication complexity and number theory to prove degree bounds. We use these to give the first tight degree bounds for a number of Boolean functions. We consider the combinatorial problem of explicit construction of Ramsey graphs. We present a simple construction of such graphs using polynomials modulo composites. This approach gives a unifying view of many known constructions,and explains why they all achieve the same bound.We show that certain approaches to this problem cannot give better bounds. Finally, we consider the algorithmic problem of interpolation for polynomials modulo composites. We present the first query-efficient algorithms for interpolation and learning under a distribution. These results rely on some new structural results about such polynomials.

Shared objects are a key component in today's large distributed systems. Linearizability is a popular consistency condition for such shared objects which gives the illusion of sequential execution of operations. The time bound of an operation is the worst-case time complexity from the operation invocation to its response. Some time bounds have been proved for certain operations on linearizable shared objects in partially synchronous systems but there are some gaps between time upper bound and lower bound for each operation. In this work, the goal is to narrow or eliminate the gaps and find optimally fast implementations. To reach this goal, we prove larger lower bounds and show smaller upper bounds (compared to 2d for all operations in previous folklore implementations) by proposing an implementation for a shared object with an arbitrary data type in distributed systems of n processes in which every message delay is bounded within [d-u, d] and the maximum skew between processes' clocks is epsilon. Considering any operation for which there exist two instances such that individually, each instance is legal but in sequence they are not, we prove a lower bound of d + min{epsilon, u, d/3}, improving from d, and show this bound is tight when epsilon < d/3 and epsilon < u. Considering any operation for which there exist k instances such that each instance separately is legal and any sequence of them is legal, but the state of the object is different after different sequences, we prove a lower bound of (1-1/k)u, improving from u/2, and show this bound is tight when k = n. A pure mutator only modifies the object but does not return anything about the object. A pure accessor does not modify the object. For a pure mutator OP1 and a pure accessor OP2, if given a set of instances of OP1, the state of the object reflects the order in which the instances occur and an instance of OP2 can detect whether an instance of OP1 occurs, we prove the sum of the time bound for OP1 and OP2 is at least d + min{epsilon, u, d/3}, improving from d. The upper bound is d + 2*epsilon from our implementation.

The Balanced Scorecard (BSC) facilitates managers to balance strategic focuses on four perspectives, on complex cause and effect relationships, and on developing more systemic aligned strategy. But some literatures showed that the BSC theory and practice had some limitations. The root of limitations is ¡§cause and effect are not closely related in time and space¡¨. And that will mislead managers to generate misperceptions of feedback information and execute wrong strategy. This research employs system dynamics as a method to overcome the limitations, and focuses on exploring the dynamic complexity of developing the BSC strategy. By two case studies, this research finds some opinions to conceptualize a theoretical framework, generate some dynamic pitfalls propositions, and summarize some dynamically aligned principles. By system dynamics method, this research builds qualitative and quantitative system dynamics models and inquires the cases¡¦ BSC strategy. And by case study method, this research follows qualitative research perspective to compare two cases and generate propositions. The conclusion, firstly, includes a conceptualized framework of ¡§improving the dynamic alignment of the balanced scorecard strategy in system dynamics¡¨, to support ¡§the theory of developing BSC with system dynamics¡¨ and enhance the long-term effectiveness of BSC strategy. Secondly, this research finds some dynamic pitfalls propositions. Lastly, this research discusses some implications on management, limitations, and future research.

To inquire into entrepreneurship, a newly-emerging and interesting subject, our research has selected Taiwan¡¦s information technology electronics components industry as research target. By gathering vast- and primary- data, and using several representative Taiwanese component manufacturers as case studies, we found the ¡¥technical-amateur¡¦ phenomenon. This paper will clearly explain the contents, contextual factors, and advantages of technical-amateur entrepreneurship. These type of entrepreneurs are so-called ¡¥technical-amateurs¡¦ because they lacked previous work experiences in the information technology industry, i.e. outsiders; they also lacked technical ability of the typical blue-collared workers and the engineers, they were previously high-level managers in the manufacturing industry. Thus technical-amateurs tend to have vast- and extended- relationship networks that can quickly transfer capitals, to form capital team and gain the assistance of venture capital to attract the technical team; they also have sharp intuition that can strategize to move toward the mainstream to maximize market benefits; they also have managerial ability that can successfully assimilate the technology team and improve production efficiency while reducing production cost. These concepts are similar to the arguments of ¡¥fitness landscape¡¦, ¡¥co-evolution¡¦, and ¡¥the establishment of shared schema¡¨. There are several important contextual factors that led to the emergence of technical-amateurs. 1) Product technology already exists, but the process technology remains to be explored; 2) Clustering of the local information technology industry, especially the existence of world-class EMS manufacturers; 3) Rapid growths of venture-capitals; 4) Mobility of technology and talents; and 5) Profitability minimization of information products. Comparing to technical entrepreneurs, technical-amateur entrepreneurs have the following advantages: 1.By occupying the advanced-guard position in the information industry, can quickly discover entrepreneurial opportunities. Outsourcing under changes in the global commodity chain and the trend toward lighter- and smaller- information products, give rise to more entrepreneurial opportunities in the component industry. Since technical-amateurs maintain close relationships with venture-capital thus can organize capital team, therefore occupying the advanced-guard position where they can quickly discover emerging opportunities. 2.Powerful Capital Reinforcements. To achieve economies of scale, newly-founded components businesses must quickly improve its productivity. But before this could happen, manufacturer must experience a learning period where budgetary deficits are unavoidable. However due to the reinforcements of the capital team, technical-amateur entrepreneurs can lead through this difficult period and into a most profitable period of significant growths.