Algebraic theory of minimal nondeterministic finite automata with applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA’s behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

The Market for Apples: A Theory of Identity and Consumption

This paper presents an economic model of the effects of identity and social norms on consumption patterns. By incorporating qualitative studies in psychology and sociology, I propose a utility function that features two components – economic (functional) and identity elements. This setup is extended to analyze a market comprising a continuum of consumers, whose identity distribution along a spectrum of binary identities is described by a Beta distribution. I also introduce the notion of salience in the context of identity and consumption decisions. The key result of the model suggests that fundamental economic parameters, such as price elasticity and market demand, can be altered by identity elements. In addition, it predicts that firms in perfectly competitive markets may associate their products with certain types of identities, in order to reduce product substitutability and attain price-setting power.

In search of a theory of integrated marketing communication

For the most part, the literature base for Integrated Marketing Communication (IMC) has developed from an applied or tactical level rather than from an intellectual or theoretical one. Since industry, practitioner and even academic studies have provided little insight into what IMC is and how it operates, our approach has been to investigate that other IMC community, that is, the academic or instructional group responsible for disseminating IMC knowledge. We proposed that the people providing course instruction and directing research activities have some basis for how they organize, consider and therefore instruct in the area of IMC. A syllabi analysis of 87 IMC units in six countries investigated the content of the unit, its delivery both physically and conceptually, and defined the audience of the unit. The study failed to discover any type of latent theoretical foundation that might be used as a base for understanding IMC. The students who are being prepared to extend, expand and enhance IMC concepts do not appear to be well-served by the curriculum we found in our research. The study concludes with a model for further IMC curriculum development.

Varieties of Asian capitalism : toward an institutional theory of Asian enterprise

In this paper we respond to calls for an institution-based perspective on strategy. With its emphasis upon mimetic, coercive, and normative isomorphism, institutional theory has earned a deterministic reputation and seems an unlikely foundation on which to construct a theory of strategy. However, a second movement in institutional theory is emerging that gives greater emphasis to creativity and agency. We develop this approach by highlighting co-evolutionary processes that are shaping the varieties of capitalism (VoC) in Asia. To do so, we examine the extent to which the VoC model can be fruitfully applied in the Asian context. In the spirit of the second movement of institutional theory, we describe three processes in which firm strategy collectively and intentionally feeds back to shape institutions: (1) filling institutional voids, (2) retarding institutional innovation, and (3) deploying institutional escape. We outline the key contributions contained in the articles of this Special Issue and discuss a research agenda generated by the VoC perspective.

A numerical method to quantify the axial shortening of vertical elements in concrete buildings

Differential axial shortening, distortion and deformation in high rise buildings is a serious concern. They are caused by three time dependent modes of volume change; “shrinkage”, “creep” and “elastic shortening” that takes place in every concrete element during and after construction. Vertical concrete components in a high rise building are sized and designed based on their strength demand to carry gravity and lateral loads. Therefore, columns and walls are sized, shaped and reinforced differently with varying concrete grades and volume to surface area ratios. These structural components may be subjected to the detrimental effects of differential axial shortening that escalates with increasing the height of buildings. This can have an adverse impact on other structural and non-structural elements. Limited procedures are available to quantify axial shortening, and the results obtained from them differ because each procedure is based on various assumptions and limited to few parameters. All these prompt to a need to develop an accurate numerical procedure to quantify the axial shortening of concrete buildings taking into account the important time varying functions of (i) construction sequence (ii) Young’s Modulus and (iii) creep and shrinkage models associated with reinforced concrete. General assumptions are refined to minimize variability of creep and shrinkage parameters to improve accuracy of the results. Finite element techniques are used in the procedure that employs time history analysis along with compression only elements to simulate staged construction behaviour. This paper presents such a procedure and illustrates it through an example. Keywords: Differential Axial Shortening, Concrete Buildings, Creep and Shrinkage, Construction Sequence, Finite Element Method.

Tests of the elaborated intrusion theory of craving and desire : features of alcohol craving during treatment for an alcohol disorder

Objectives. We tested predictions from the elaborated intrusion (EI) theory of desire, which distinguishes intrusive thoughts and elaborations, and emphasizes the importance of imagery. Secondarily, we undertook preliminary evaluations of the Alcohol Craving Experience (ACE) questionnaire, a new measure based on EI Theory. Methods. Participants (N ¼ 232) were in correspondence-based treatment trials for alcohol abuse or dependence. The study used retrospective reports obtained early in treatment using the ACE, and daily self-monitoring of urges, craving, mood and alcohol consumption. Results. The ACE displayed high internal consistency and test – retest reliability and sound relationships with self-monitored craving, and was related to Baseline alcohol dependence, but not to consumption. Imagery during craving was experienced by 81%,with 2.3 senses involved on average. More frequent imagery was associated with longer episode durations and stronger craving. Transient intrusive thoughts were reported by 87% of respondents, and were more common if they frequently attempted to stop alcohol cognitions. Associations between average daily craving and weekly consumption were seen. Depression and negative mood were associated with more frequent, stronger and longer lasting desires for alcohol. Conclusions. Results supported the distinction of automatic and controlled processes in craving, together with the importance of craving imagery. They were also consistent with prediction of consumption from cross-situational averages of craving, and with positive associations between craving and negative mood. However, this study’s retrospective reporting and correlational design require that its results be interpreted cautiously. Research using ecological momentary measures and laboratory manipulations is needed before confident inferences about causality can be made.

Imaginary relish and exquisite torture : the elaborated intrusion theory of desire

The authors argue that human desire involves conscious cognition that has strong affective connotation and is potentially involved in the determination of appetitive behavior rather than being epiphenomenal to it. Intrusive thoughts about appetitive targets are triggered automatically by external or physiological cues and by cognitive associates. When intrusions elicit significant pleasure or relief, cognitive elaboration usually ensues. Elaboration competes with concurrent cognitive tasks through retrieval of target related information and its retention in working memory. Sensory images are especially important products of intrusion and elaboration because they simulate the sensory and emotional qualities of target acquisition. Desire images are momentarily rewarding but amplify awareness of somatic and emotional deficits. Effects of desires on behavior are moderated by competing incentives, target availability, and skills. The theory provides a coherent account of existing data and suggests new directions for research and treatment.