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.

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.

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.

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.

Syllable-timing in Brazilian Portuguese: uma crítica a Roy Major

This paper reintroduces the discussion about stress-timing in Brazilian Portuguese (BP). It begins by surveying some phonetic and phonological issues raised by the syllable- vs stress-timed dichotomy which culminated with the emergence of the p-center notion. Strict considerations of timing of V-V units and stress groups are taken into account to analyze the long term coupling of two basic oscillators (vowel and stress flow). This coupling allows a two-parameter characterization of language rhythms (coupling strength and speech rate) revealing that BP utterances present a high-degree of syllable-timing. A comparison with other languages, including European Portuguese, is also presented. The results analyzed indicate that Major's arguments for considering Portuguese (sic) as stress-timing are misleading.

The Effect of Spatial Scale on Predicting Time Series: A Study on Epidemiological System Identification

A susceptible-infective-recovered (SIR) epidemiological model based on probabilistic cellular automaton (PCA) is employed for simulating the temporal evolution of the registered cases of chickenpox in Arizona, USA, between 1994 and 2004. At each time step, every individual is in one of the states S, I, or R. The parameters of this model are the probabilities of each individual (each cell forming the PCA lattice ) passing from a state to another state. Here, the values of these probabilities are identified by using a genetic algorithm. If nonrealistic values are allowed to the parameters, the predictions present better agreement with the historical series than if they are forced to present realistic values. A discussion about how the size of the PCA lattice affects the quality of the model predictions is presented. Copyright (C) 2009 L. H. A. Monteiro et al.

System Identification and Prediction of Dengue Fever Incidence in Rio de Janeiro

Identification, prediction, and control of a system are engineering subjects, regardless of the nature of the system. Here, the temporal evolution of the number of individuals with dengue fever weekly recorded in the city of Rio de Janeiro, Brazil, during 2007, is used to identify SIS (susceptible-infective-susceptible) and SIR (susceptible-infective-removed) models formulated in terms of cellular automaton (CA). In the identification process, a genetic algorithm (GA) is utilized to find the probabilities of the state transition S -> I able of reproducing in the CA lattice the historical series of 2007. These probabilities depend on the number of infective neighbors. Time-varying and non-time-varying probabilities, three different sizes of lattices, and two kinds of coupling topology among the cells are taken into consideration. Then, these epidemiological models built by combining CA and GA are employed for predicting the cases of sick persons in 2008. Such models can be useful for forecasting and controlling the spreading of this infectious disease.

Cooperative scattering and radiation pressure force in dense atomic clouds

Atomic clouds prepared in ""timed Dicke"" states, i.e. states where the phase of the oscillating atomic dipole moments linearly varies along one direction of space, are efficient sources of superradiant light emission [Scully et al., Phys. Rev. Lett. 96, 010501 (2006)]. Here, we show that, in contrast to previous assertions, timed Dicke states are not the states automatically generated by incident laser light. In reality, the atoms act back on the driving field because of the finite refraction of the cloud. This leads to nonuniform phase shifts, which, at higher optical densities, dramatically alter the cooperative scattering properties, as we show by explicit calculation of macroscopic observables, such as the radiation pressure force.

Age-related difference on weight transfer during unconstrained standing

The ability to transfer weight from one lower limb to the other is essential for the execution of daily life activities and little is known about how weight transfer during unconstrained natural standing is affected by age. This study examined the weight transfer ability of elderly individuals during unconstrained standing (for 30 mill) in comparison to young adults. The subjects (19 healthy elderly adults, range 65-80 years, and 19 healthy young adults, range 18-30 years) stood with each foot on a separate force plate and were allowed to change their posture freely at any time. The limits of stability and base of support width during standing, measures of mobility (using the timed up and go and the preferred walking speed tests), and fear of falling were also measured. In comparison to the young adults, during unconstrained standing the elderly adults produced four times fewer weight transfers of large amplitude (greater than,half of their body weight). The limits of stability and base of support width were significantly smaller for the elderly adults but there were no significant differences in the measures of mobility and in the fear of falling score compared to young adults. The observed significant age-related decrease in the use of weight transfer during unconstrained standing, despite any difference in the measured mobility of the subjects, suggests that this task reveals unnoticed and subtle differences in postural control, which may help to better understand age related impairments in balance that the elderly population experiences. (C) 2010 Elsevier B.V. All rights reserved.

Efficacy and safety of concurrent training in systemic sclerosis

Pinto, ALS, Oliveira, NC, Gualano, B, Christmann, RB, Painelli, VS, Artioli, GG, Prado, DML, and Lima, FR. Efficacy and safety of concurrent training in systemic sclerosis. J Strength Cond Res 25(5): 1423-1428, 2011-The optimal training model for patients with systemic sclerosis (SSc) is unknown. In this study, we aimed to investigate the effects of a 12-week combined resistance and aerobic training program (concurrent training) in SSc patients. Eleven patients with no evidence of pulmonary involvement were recruited for the exercise program. Lower and upper limb dynamic strengths (assessed by 1 repetition maximum [1RM] of a leg press and bench press, respectively), isometric strength (assessed by back pull and handgrip tests), balance and mobility (assessed by the timed up-and-go test), muscle function (assessed by the timed-stands test), Rodnan score, digital ulcers, Rayland`s phenomenon, and blood markers of muscle inflammation (creatine kinase and aldolase) were assessed at baseline and after the 12-week program. Exercise training significantly enhanced the 1RM leg press (41%) and 1RM bench press (13%) values and back pull (24%) and handgrip strength (11%). Muscle function was also improved (15%), but balance and mobility were not significantly changed. The time-to-exhaustion was increased (46.5%, p = 0.0004), the heart rate at rest condition was significantly reduced, and the workload and time of exercise at ventilatory thresholds and peak of exercise were increased. However, maximal and submaximal (V)over dotO(2) were unaltered (p > 0.05). The Rodnan score was unchanged, and muscle enzymes remained within normal levels. No change was observed in digital ulcers and Raynaud`s phenomenon. This is the first study to demonstrate that a 12-week concurrent training program is safe and substantially improves muscle strength, function, and aerobic capacity in SSc patients.

A Procedure for Semantic Querying in the Adaptive Formalism

This paper contains a new proposal for the definition of the fundamental operation of query under the Adaptive Formalism, one capable of locating functional nuclei from descriptions of their semantics. To demonstrate the method`s applicability, an implementation of the query procedure constrained to a specific class of devices is shown, and its asymptotic computational complexity is discussed.

A vaccination game based on public health actions and personal decisions

Susceptible-infective-removed (SIR) models are commonly used for representing the spread of contagious diseases. A SIR model can be described in terms of a probabilistic cellular automaton (PCA), where each individual (corresponding to a cell of the PCA lattice) is connected to others by a random network favoring local contacts. Here, this framework is employed for investigating the consequences of applying vaccine against the propagation of a contagious infection, by considering vaccination as a game, in the sense of game theory. In this game, the players are the government and the susceptible newborns. In order to maximize their own payoffs, the government attempts to reduce the costs for combating the epidemic, and the newborns may be vaccinated only when infective individuals are found in their neighborhoods and/or the government promotes an immunization program. As a consequence of these strategies supported by cost-benefit analysis and perceived risk, numerical simulations show that the disease is not fully eliminated and the government implements quasi-periodic vaccination campaigns. (C) 2011 Elsevier B.V. All rights reserved.

Who should wear mask against airborne infections? Altering the contact network for controlling the spread of contagious diseases

There are several ways of controlling the propagation of a contagious disease. For instance, to reduce the spreading of an airborne infection, individuals can be encouraged to remain in their homes and/or to wear face masks outside their domiciles. However, when a limited amount of masks is available, who should use them: the susceptible subjects, the infective persons or both populations? Here we employ susceptible-infective-recovered (SIR) models described in terms of ordinary differential equations and probabilistic cellular automata in order to investigate how the deletion of links in the random complex network representing the social contacts among individuals affects the dynamics of a contagious disease. The inspiration for this study comes from recent discussions about the impact of measures usually recommended by health public organizations for preventing the propagation of the swine influenza A (H1N1) virus. Our answer to this question can be valid for other eco-epidemiological systems. (C) 2010 Elsevier BM. All rights reserved.