On OBDD Transformations Representing Finite State Automata

We present OBDD transformation problem representing finite labeled transition systems corresponding to some congruence relation. Transformations are oriented toward obtaining the OBDD of a minimized transition system for this congruence relation.

Timed Transition Automata as Numerical Planning Domain

A general technique for transforming a timed finite state automaton into an equivalent automated planning domain based on a numerical parameter model is introduced. Timed transition automata have many applications in control systems and agents models; they are used to describe sequential processes, where actions are labelling by automaton transitions subject to temporal constraints. The language of timed words accepted by a timed automaton, the possible sequences of system or agent behaviour, can be described in term of an appropriate planning domain encapsulating the timed actions patterns and constraints. The time words recognition problem is then posed as a planning problem where the goal is to reach a final state by a sequence of actions, which corresponds to the timed symbols labeling the automaton transitions. The transformation is proved to be correct and complete and it is space/time linear on the automaton size. Experimental results shows that the performance of the planning domain obtained by transformation is scalable for real world applications. A major advantage of the planning based approach, beside of the solving the parsing problem, is to represent in a single automated reasoning framework problems of plan recognitions, plan synthesis and plan optimisation.

Minimization of Reactive Probabilistic Automata

The problem of finite automata minimization is important for software and hardware designing. Different types of automata are used for modeling systems or machines with finite number of states. The limitation of number of states gives savings in resources and time. In this article we show specific type of probabilistic automata: the reactive probabilistic finite automata with accepting states (in brief the reactive probabilistic automata), and definitions of languages accepted by it. We present definition of bisimulation relation for automata's states and define relation of indistinguishableness of automata states, on base of which we could effectuate automata minimization. Next we present detailed algorithm reactive probabilistic automata’s minimization with determination of its complexity and analyse example solved with help of this algorithm.

Building theory at the intersection of ecological sustainability and strategic management

This article builds theory at the intersection of ecological sustainability and strategic management literature—specifically, in relation to dynamic capabilities literature. By combining industrial organization economics–based, resource-based, and dynamic capability–based views, it is possible to develop a better understanding of the strategies that businesses may follow, depending on their managers’ assumptions about ecological sustainability. To develop innovative strategies for ecological sustainability, the dynamic capabilities framework needs to be extended. In particular, the sensing–seizing–maintaining competitiveness framework should operate not only within the boundaries of a business ecosystem but in relation to global biophysical ecosystems; in addition, two more dynamic capabilities should be added, namely, remapping and reaping. This framework can explicate core managerial beliefs about ecological sustainability. Finally, this approach offers opportunities for managers and academics to identify, categorize, and exploit business strategies for ecological sustainability.

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.

Forecasting enrollment in differential assessment programs using cellular automata

Urban growth models have been used for decades to forecast urban development in metropolitan areas. Since the 1990s cellular automata, with simple computational rules and an explicitly spatial architecture, have been heavily utilized in this endeavor. One such cellular-automata-based model, SLEUTH, has been successfully applied around the world to better understand and forecast not only urban growth but also other forms of land-use and land-cover change, but like other models must be fed important information about which particular lands in the modeled area are available for development. Some of these lands are in categories for the purpose of excluding urban growth that are difficult to quantify since their function is dictated by policy. One such category includes voluntary differential assessment programs, whereby farmers agree not to develop their lands in exchange for significant tax breaks. Since they are voluntary, today’s excluded lands may be available for development at some point in the future. Mapping the shifting mosaic of parcels that are enrolled in such programs allows this information to be used in modeling and forecasting. In this study, we added information about California’s Williamson Act into SLEUTH’s excluded layer for Tulare County. Assumptions about the voluntary differential assessments were used to create a sophisticated excluded layer that was fed into SLEUTH’s urban growth forecasting routine. The results demonstrate not only a successful execution of this method but also yielded high goodness-of-fit metrics for both the calibration of enrollment termination as well as the urban growth modeling itself.

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.

Annotated record of the detailed examination of Mn deposits from COCOTOW Expedition stations in the intersection of the Siqueiros Transform Fault and the East Pacific Rise

A near-bottom geological and geophysical survey was conducted at the western intersection of the Siqueiros Transform Fault and the East Pacific Rise. Transform-fault shear appears to distort the east flank of the rise crest in an area north of the fracture zone. In ward-facing scarps trend 335° and do not parallel the regional axis of spreading. Small-scale scarps reveal a hummocky bathymetry. The center of spreading is not a central peak but rather a 20-40 m deep, 1 km wide valley superimposed upon an 8 km wide ridge-crest horst. Small-scale topography indicates widespread volcanic flows within the valley. Two 0.75 km wide blocks flank the central valley. Fault scarps are more dominant on the western flank. Their alignment shifts from directions intermediate to parallel to the regional axis of spreading (355°). A median ridge within the fracture zone has a fault-block topography similar to that of the East Pacific Rise to the north. Dominant eastward-facing scarps trending 335° are on the west flank. A central depression, 1 km wide and 30 m deep, separates the dominantly fault-block regime of the west from the smoother topography of the east flank. This ridge originated by uplift due to faulting as well as by volcanism. Detailed mapping was concentrated in a perched basin (Dante's Hole) at the intersection of the rise crest and the fracture zone. Structural features suggest that Dante's Hole is an area subject to extreme shear and tensional drag resulting from transition between non-rigid and rigid crustal behavior. Normal E-W crustal spreading is probably taking place well within the northern confines of the basin. Possible residual spreading of this isolated rise crest coupled with shear drag within the transform fault could explain the structural isolation of Dante's Hole from the remainder of the Siqueiros Transform Fault.

Automata and men : the shift towards a human ideal in the fiction of Wyndham Lewis

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Polynômes de Kazhdan-Lusztig et cohomologie d'intersection des variétés de drapeaux

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Rephasing of the intersection of city hall of Leiria

This project proposes two possible solutions for the phasing plan of the intersection near the City Hall of Leiria and presents the calculations of the cycle length and the intersection delay for both of them. The main goal of these solutions is to optimize the global functioning of the intersection. Since the number of cars that use an intersection is will fluctuate with time, when using pre-timed traffic lights, adjustments are needed to the settings of the traffic signals, to assure the accommodation of the present traffic flows in the intersection under acceptable conditions for drivers.

Automata and men : the shift towards a human ideal in the fiction of Wyndham Lewis

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Polynômes de Kazhdan-Lusztig et cohomologie d'intersection des variétés de drapeaux

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Roads to Health in Nigeria – Understanding the Intersection of Culture and Healing

The most important attribute for which we all aspire as human beings is good health because it enables us to undertake different forms of activities of daily living. The emergence of scientific knowledge in Western societies has enabled us to explore and define several parameters of “health” by drawing boundaries around factors that are known to impact the achievement of good health. For example, the World Health Organization defined health by taking physical and psychological factors into consideration.

Chaos decomposition and gap renormalization of brownian self-intersection local times

We study the chaos decomposition of self-intersection local times and their regularization, with a particular view towards Varadhan's renormalization for the planar Edwards model.