Complexité raffinée du problème d'intersection d'automates

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

Modélisation de répartition d’espèces aviaires et de feux en forêt boréale du Québec dans un contexte de changement climatique

Les changements climatiques prennent une importance grandissante dans l’étude des phénomènes spatiaux à grande échelle. Plusieurs experts affirment que les changements climatiques seront un des principaux moteurs de changement écologique dans les prochaines décennies et que leurs conséquences seront inévitables. Ces changements se manifesteront sur le milieu physique par la fonte des calottes glaciaires, le dégel du pergélisol, l’instabilité des versants montagneux en zone de pergélisol, l’augmentation de l’intensité, de la sévérité et de la fréquence des événements climatiques extrêmes tels les feux de forêt. Les changements climatiques se manifesteront aussi sur le milieu biologique, tel la modification de la durée de la saison végétative, l’augmentation des espèces exotiques invasives et les changements dans la distribution en espèces vivantes. Deux aspects sont couverts par cette étude : 1) les changements dans la répartition spatiale de 39 espèces d’oiseaux et 2) les modifications dans les patrons spatiaux des feux, en forêt boréale québécoise, tous deux dans l’horizon climatique de 2100. Une approche de modélisation statistique démontre que la répartition spatiale des oiseaux de la forêt boréale est fortement liée à des variables bioclimatiques (R2adj = 0.53). Ces résultats permettent d’effectuer des modélisations bioclimatiques pour le gros-bec errant et la mésange à tête noire quivoient une augmentation de la limite nordique de distribution de l’espèce suivant l’intensité du réchauffement climatique. Finalement, une modélisation spatialement explicite par automate cellulaire permet de démontrer comment les changements climatiques induiront une augmentation dans la fréquence de feux de forêt et dans la superficie brûlée en forêt boréale du Québec.

Reinforcement Learning Approaches to Power System Scheduling

One major component of power system operation is generation scheduling. The objective of the work is to develop efficient control strategies to the power scheduling problems through Reinforcement Learning approaches. The three important active power scheduling problems are Unit Commitment, Economic Dispatch and Automatic Generation Control. Numerical solution methods proposed for solution of power scheduling are insufficient in handling large and complex systems. Soft Computing methods like Simulated Annealing, Evolutionary Programming etc., are efficient in handling complex cost functions, but find limitation in handling stochastic data existing in a practical system. Also the learning steps are to be repeated for each load demand which increases the computation time.Reinforcement Learning (RL) is a method of learning through interactions with environment. The main advantage of this approach is it does not require a precise mathematical formulation. It can learn either by interacting with the environment or interacting with a simulation model. Several optimization and control problems have been solved through Reinforcement Learning approach. The application of Reinforcement Learning in the field of Power system has been a few. The objective is to introduce and extend Reinforcement Learning approaches for the active power scheduling problems in an implementable manner. The main objectives can be enumerated as:(i) Evolve Reinforcement Learning based solutions to the Unit Commitment Problem.(ii) Find suitable solution strategies through Reinforcement Learning approach for Economic Dispatch. (iii) Extend the Reinforcement Learning solution to Automatic Generation Control with a different perspective. (iv) Check the suitability of the scheduling solutions to one of the existing power systems.First part of the thesis is concerned with the Reinforcement Learning approach to Unit Commitment problem. Unit Commitment Problem is formulated as a multi stage decision process. Q learning solution is developed to obtain the optimwn commitment schedule. Method of state aggregation is used to formulate an efficient solution considering the minimwn up time I down time constraints. The performance of the algorithms are evaluated for different systems and compared with other stochastic methods like Genetic Algorithm.Second stage of the work is concerned with solving Economic Dispatch problem. A simple and straight forward decision making strategy is first proposed in the Learning Automata algorithm. Then to solve the scheduling task of systems with large number of generating units, the problem is formulated as a multi stage decision making task. The solution obtained is extended in order to incorporate the transmission losses in the system. To make the Reinforcement Learning solution more efficient and to handle continuous state space, a fimction approximation strategy is proposed. The performance of the developed algorithms are tested for several standard test cases. Proposed method is compared with other recent methods like Partition Approach Algorithm, Simulated Annealing etc.As the final step of implementing the active power control loops in power system, Automatic Generation Control is also taken into consideration.Reinforcement Learning has already been applied to solve Automatic Generation Control loop. The RL solution is extended to take up the approach of common frequency for all the interconnected areas, more similar to practical systems. Performance of the RL controller is also compared with that of the conventional integral controller.In order to prove the suitability of the proposed methods to practical systems, second plant ofNeyveli Thennal Power Station (NTPS IT) is taken for case study. The perfonnance of the Reinforcement Learning solution is found to be better than the other existing methods, which provide the promising step towards RL based control schemes for practical power industry.Reinforcement Learning is applied to solve the scheduling problems in the power industry and found to give satisfactory perfonnance. Proposed solution provides a scope for getting more profit as the economic schedule is obtained instantaneously. Since Reinforcement Learning method can take the stochastic cost data obtained time to time from a plant, it gives an implementable method. As a further step, with suitable methods to interface with on line data, economic scheduling can be achieved instantaneously in a generation control center. Also power scheduling of systems with different sources such as hydro, thermal etc. can be looked into and Reinforcement Learning solutions can be achieved.

Learning analysis by reduction from positive data

Analysis by reduction is a linguistically motivated method for checking correctness of a sentence. It can be modelled by restarting automata. In this paper we propose a method for learning restarting automata which are strictly locally testable (SLT-R-automata). The method is based on the concept of identification in the limit from positive examples only. Also we characterize the class of languages accepted by SLT-R-automata with respect to the Chomsky hierarchy.

On Alternating Non-Context-Free Grammars

We study several extensions of the notion of alternation from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. Thereby new grammatical characterizations are obtained for the class of languages that are accepted by alternating pushdown automata.

20. Theorietag der GI-Fachgruppe "Automaten und Formale Sprachen''

Die Fachgruppe AFS (früher Fachgruppe 0.1.5) der Gesellschaft für Informatik veranstaltet seit 1991 einmal im Jahr ein Treffen der Fachgruppe im Rahmen eines Theorietags, der traditionell eineinhalb Tage dauert. Seit dem Jahr 1996 wird dem eigentlichen Theorietag noch ein eintägiger Workshop zu speziellen Themen der theoretischen Informatik vorangestellt. In diesem Jahr wurde der Theorietag vom Fachgebiet "Theoretische Informatik" des Fachbereichs Elektrotechnik/Informatik der Universität Kassel organisiert. Er fand vom 29.9. bis 1.10.2010 in Baunatal bei Kassel statt. Dabei stand der begleitende Workshop unter dem allgemeinen Thema "Ausgewählte Themen der Theoretischen Informatik". Als Vortragende für diesen Workshop konnten Carsten Damm (Göttingen), Markus Holzer (Giessen), Peter Leupold (Kassel), Martin Plátek (Prag) und Heribert Vollmer (Hannover) gewonnen werden. Das Programm des eigentlichen Theorietags bestand aus 20 Vorträgen sowie der Sitzung der Fachgruppe AFS. In diesem Band finden sich die Zusammenfassungen aller Vorträge sowohl des Workshops als auch des Theorietags. Desweiteren enthält er das Programm und die Liste aller Teilnehmer.

Programmable Self-Assembly: Constructing Global Shape using Biologically-inspire

In this thesis I present a language for instructing a sheet of identically-programmed, flexible, autonomous agents (``cells'') to assemble themselves into a predetermined global shape, using local interactions. The global shape is described as a folding construction on a continuous sheet, using a set of axioms from paper-folding (origami). I provide a means of automatically deriving the cell program, executed by all cells, from the global shape description. With this language, a wide variety of global shapes and patterns can be synthesized, using only local interactions between identically-programmed cells. Examples include flat layered shapes, all plane Euclidean constructions, and a variety of tessellation patterns. In contrast to approaches based on cellular automata or evolution, the cell program is directly derived from the global shape description and is composed from a small number of biologically-inspired primitives: gradients, neighborhood query, polarity inversion, cell-to-cell contact and flexible folding. The cell programs are robust, without relying on regular cell placement, global coordinates, or synchronous operation and can tolerate a small amount of random cell death. I show that an average cell neighborhood of 15 is sufficient to reliably self-assemble complex shapes and geometric patterns on randomly distributed cells. The language provides many insights into the relationship between local and global descriptions of behavior, such as the advantage of constructive languages, mechanisms for achieving global robustness, and mechanisms for achieving scale-independent shapes from a single cell program. The language suggests a mechanism by which many related shapes can be created by the same cell program, in the manner of D'Arcy Thompson's famous coordinate transformations. The thesis illuminates how complex morphology and pattern can emerge from local interactions, and how one can engineer robust self-assembly.

Estado situacional de los modelos basados en agentes y su impacto en la investigación organizacional

En un mundo hiperconectado, dinámico y cargado de incertidumbre como el actual, los métodos y modelos analíticos convencionales están mostrando sus limitaciones. Las organizaciones requieren, por tanto, herramientas útiles que empleen tecnología de información y modelos de simulación computacional como mecanismos para la toma de decisiones y la resolución de problemas. Una de las más recientes, potentes y prometedoras es el modelamiento y la simulación basados en agentes (MSBA). Muchas organizaciones, incluidas empresas consultoras, emplean esta técnica para comprender fenómenos, hacer evaluación de estrategias y resolver problemas de diversa índole. Pese a ello, no existe (hasta donde conocemos) un estado situacional acerca del MSBA y su aplicación a la investigación organizacional. Cabe anotar, además, que por su novedad no es un tema suficientemente difundido y trabajado en Latinoamérica. En consecuencia, este proyecto pretende elaborar un estado situacional sobre el MSBA y su impacto sobre la investigación organizacional.

La transformació del paisatge litoral de la Costa Brava: Anàlisi de l'evolució (1956-2003), diagnosi de l'estat actual i prognosi de futur

En la tesi es presenta una anàlisi de l'evolució dels canvis succeïts en el paisatge costaner de la Costa Brava (22 municipis litorals) en els darrers cinquanta anys (1956-2003); un estudi de la seva estructura ecopaisatgística, actual i passada, amb una especial èmfasi en la diagnosi de les conseqüències geoambientals de l'esclat urbanístic iniciat a la dècada de 1960, i s'ha determinat quina ha estat la tendència de canvi en els darrers vint-i-cinc anys la qual s'ha utilitzat per a elaborar models explicatius de la dinàmica territorial seguida i projectar-los cap al futur tot dissenyant escenaris probables. A les Bases teòriques s'exposa en quina parcel·la del coneixement científic es situa aquesta recerca i es repassa l'evolució dels diferents corrents i enfocaments que han precedit, dins la Ciència Geogràfica, els estudis sobre transformació del paisatge. Es posa especial en els principis i metodologies que plantegen les dues escoles d'anàlisi del paisatge en que es basa aquesta tesi: la Landscape Ecology i la estructurada a l'entorn del programa internacional Land Use and Land Cover Change (LUCC). S'ha dissenyat una pauta metodològica per a l'anàlisi paisatgística d'un territori a diferents escales: des de l'àmbit regional de tota la Costa Brava (66.230 ha), on es poden detectar les tendències generals, fins l'estudi detallat a escala local, on s'ha pres com a àrea d'estudi tres municipis del centre de la Costa Brava (6.960 Ha): Palamós, Calonge i Castell-Platja d'Aro. Els principals resultats obtinguts són els següents: Una cartografia d'usos i cobertes del sòl de tres períodes temporals i la conseqüent interpretació espacial per a cada etapa: 1957 (situació preturística), 1980 (inici de les actuacions dels ajuntaments democràtics) i 2003 (actualitat). Una anàlisi quantitativa de la transformació del paisatge i de les relacions espacials associades al canvi, a partir de la cartografia d'usos i cobertes del sòl dels tres períodes mapificats (1956, 1980, 2003). Amb l'objectiu d'arribar a definir quina ha estat la dinàmica dels canvis ocorreguts al llarg dels darrers gairebé cinquanta anys. Una anàlisi de l'estructura del mosaic paisatgístic de cadascun dels talls temporals per mitjà de l'aplicació dels principals índexs de l'Ecologia del Paisatge. S'ha analitzat la geometria de la conversió dels usos del sòl i s'han posat de manifest les repercussions ecològiques i paisatgístiques d'aquests canvis. Per una banda, a partir del càlcul i interpretació dels índexos esmentats s'ha analitzat l'evolució de la morfologia i la distribució territorial dels quatre principals usos i cobertes del sòl de la Costa Brava. Per l'altra, per a la Costa Brava centre s'ha analitzat l'estat dels dos sistemes naturals del litoral amb més pressió antròpica: la franja estrictament costanera i les masses forestals. Respecte als tres municipis de la Costa Brava centre s'han tingut en compte en l'anàlisi de l'evolució del paisatge a escala local, les actuacions desenvolupades en l'àmbit urbanístic municipal i les seves conseqüències paisatgístiques i ambientals. A partir de la informació ja processada, s'han detectat les tendències de canvi a partir de models de canvi d'usos i cobertes del sòl. S'han incorporat també els factors biofísics i antròpics, socials i econòmics, condicionants i responsables d'una determinada utilització del territori en cadascun dels tres períodes. Mitjançant l'anàlisi multivariable s'ha intentat descobrir el conjunt de factors que influencien en la taxa i el patró espacial de canvi d'usos i les seves conseqüències territorials. Finalment s'ha aplicat un model de simulació, basat en els automatismes cel·lulars de Markov, per tal de projectar les tendències de canvi i plantejar escenaris futurs, una eina bàsica per a la planificació futura del territori i per al control de les problemàtiques ambientals. Aquestes mesures serveixen per a definir, per a la Costa Brava centre, un patró espacial dels canvis d'usos del sòl a nivell local, i, per al conjunt de la Costa Brava, per a predir, mitjançant models de simulació quantitativa, els possibles desenvolupaments i per estimar els impactes.

Negative correlations between control performance and verbalizable knowledge: indicators for implicit learning in process control tasks?

Negative correlations between task performance in dynamic control tasks and verbalizable knowledge, as assessed by a post-task questionnaire, have been interpreted as dissociations that indicate two antagonistic modes of learning, one being “explicit”, the other “implicit”. This paper views the control tasks as finite-state automata and offers an alternative interpretation of these negative correlations. It is argued that “good controllers” observe fewer different state transitions and, consequently, can answer fewer post-task questions about system transitions than can “bad controllers”. Two experiments demonstrate the validity of the argument by showing the predicted negative relationship between control performance and the number of explored state transitions, and the predicted positive relationship between the number of explored state transitions and questionnaire scores. However, the experiments also elucidate important boundary conditions for the critical effects. We discuss the implications of these findings, and of other problems arising from the process control paradigm, for conclusions about implicit versus explicit learning processes.

An agent based approach to distributed task modeling for co-operative task support

This paper describes the design and implementation of an agent based network for the support of collaborative switching tasks within the control room environment of the National Grid Company plc. This work includes aspects from several research disciplines, including operational analysis, human computer interaction, finite state modelling techniques, intelligent agents and computer supported co-operative work. Aspects of these procedures have been used in the analysis of collaborative tasks to produce distributed local models for all involved users. These models have been used as the basis for the production of local finite state automata. These automata have then been embedded within an agent network together with behavioural information extracted from the task and user analysis phase. The resulting support system is capable of task and communication management within the transmission despatch environment.

Flood Risk Assessment in Coastal Drainage Basins through a Multivariate Analysis within a GIS-Based Model

This paper presents a GIS-based multicriteria flood risk assessment and mapping approach applied to coastal drainage basins where hydrological data are not available. It involves risk to different types of possible processes: coastal inundation (storm surge), river, estuarine and flash flood, either at urban or natural areas, and fords. Based on the causes of these processes, several environmental indicators were taken to build-up the risk assessment. Geoindicators include geological-geomorphologic proprieties of Quaternary sedimentary units, water table, drainage basin morphometry, coastal dynamics, beach morphodynamics and microclimatic characteristics. Bioindicators involve coastal plain and low slope native vegetation categories and two alteration states. Anthropogenic indicators encompass land use categories properties such as: type, occupation density, urban structure type and occupation consolidation degree. The selected indicators were stored within an expert Geoenvironmental Information System developed for the State of Sao Paulo Coastal Zone (SIIGAL), which attributes were mathematically classified through deterministic approaches, in order to estimate natural susceptibilities (Sn), human-induced susceptibilities (Sa), return period of rain events (Ri), potential damages (Dp) and the risk classification (R), according to the equation R=(Sn.Sa.Ri).Dp. Thematic maps were automatically processed within the SIIGAL, in which automata cells (""geoenvironmental management units"") aggregating geological-geomorphologic and land use/native vegetation categories were the units of classification. The method has been applied to the Northern Littoral of the State of Sao Paulo (Brazil) in 32 small drainage basins, demonstrating to be very useful for coastal zone public politics, civil defense programs and flood management.

An extinction-survival-type phase transition in the probabilistic cellular automaton p182-q200

We investigate the critical behaviour of a probabilistic mixture of cellular automata (CA) rules 182 and 200 (in Wolfram`s enumeration scheme) by mean-field analysis and Monte Carlo simulations. We found that as we switch off one CA and switch on the other by the variation of the single parameter of the model, the probabilistic CA (PCA) goes through an extinction-survival-type phase transition, and the numerical data indicate that it belongs to the directed percolation universality class of critical behaviour. The PCA displays a characteristic stationary density profile and a slow, diffusive dynamics close to the pure CA 200 point that we discuss briefly. Remarks on an interesting related stochastic lattice gas are addressed in the conclusions.

Critical behavior of a contact process with aperiodic transition rates

We performed Monte Carlo simulations to investigate the steady-state critical behavior of a one-dimensional contact process with an aperiodic distribution of rates of transition. As in the presence of randomness, spatial fluctuations can lead to changes of critical behavior. For sufficiently weak fluctuations, we give numerical evidence to show that there is no departure from the universal critical behavior of the underlying uniform model. For strong spatial fluctuations, the analysis of the data indicates a change of critical universality class.

FAST, PARALLEL AND SECURE CRYPTOGRAPHY ALGORITHM USING LORENZ`S ATTRACTOR

A novel cryptography method based on the Lorenz`s attractor chaotic system is presented. The proposed algorithm is secure and fast, making it practical for general use. We introduce the chaotic operation mode, which provides an interaction among the password, message and a chaotic system. It ensures that the algorithm yields a secure codification, even if the nature of the chaotic system is known. The algorithm has been implemented in two versions: one sequential and slow and the other, parallel and fast. Our algorithm assures the integrity of the ciphertext (we know if it has been altered, which is not assured by traditional algorithms) and consequently its authenticity. Numerical experiments are presented, discussed and show the behavior of the method in terms of security and performance. The fast version of the algorithm has a performance comparable to AES, a popular cryptography program used commercially nowadays, but it is more secure, which makes it immediately suitable for general purpose cryptography applications. An internet page has been set up, which enables the readers to test the algorithm and also to try to break into the cipher.