Potassium-Lead-Switched G-Quadruplexes: A New Class of DNA Logic Gates

A cation-driven allosteric G-quadruplex DNAzyme (PW17) was utilized to devise a conceptually new class of DNA logic gate based on cation-tuned ligand binding and release. K+ favors the binding of hemin to parallel-stranded PW17, thereby promoting the DNAzyme activity, whereas Pb2+ induces PW17 to undergo a parallel-to-antiparallel conformation transition and thus drives hemin to release from the G-quadruplex, deactivating the DNAzyme. Such a K+-Pb2+ switched G-quadruplex, in fact, functions as a two-input INHIBIT logic gate. With the introduction of another input EDTA, this G-quadruplex can be further utilized to construct a reversibly operated IMPLICATION gate.

Information Processing and Transmission in Cellular Automata

A cellular automaton is an iterative array of very simple identical information processing machines called cells. Each cell can communicate with neighboring cells. At discrete moments of time the cells can change from one state to another as a function of the states of the cell and its neighbors. Thus on a global basis, the collection of cells is characterized by some type of behavior. The goal of this investigation was to determine just how simple the individual cells could be while the global behavior achieved some specified criterion of complexity ??ually the ability to perform a computation or to reproduce some pattern. The chief result described in this thesis is that an array of identical square cells (in two dimensions), each cell of which communicates directly with only its four nearest edge neighbors and each of which can exist in only two states, can perform any computation. This computation proceeds in a straight forward way. A configuration is a specification of the states of all the cells in some area of the iterative array. Another result described in this thesis is the existence of a self-reproducing configuration in an array of four-state cells, a reduction of four states from the previously known eight-state case. The technique of information processing in cellular arrays involves the synthesis of some basic components. Then the desired behaviors are obtained by the interconnection of these components. A chapter on components describes some sets of basic components. Possible applications of the results of this investigation, descriptions of some interesting phenomena (for vanishingly small cells), and suggestions for further study are given later.

Cellular automata and non-static image processing for embodied robot systems on a massively parallel processor array

Huelse, M, Barr, D R W, Dudek, P: Cellular Automata and non-static image processing for embodied robot systems on a massively parallel processor array. In: Adamatzky, A et al. (eds) AUTOMATA 2008, Theory and Applications of Cellular Automata. Luniver Press, 2008, pp. 504-510. Sponsorship: EPSRC

Building Responsive Systems from Physically-correct Specifications

Predictability - the ability to foretell that an implementation will not violate a set of specified reliability and timeliness requirements - is a crucial, highly desirable property of responsive embedded systems. This paper overviews a development methodology for responsive systems, which enhances predictability by eliminating potential hazards resulting from physically-unsound specifications. The backbone of our methodology is the Time-constrained Reactive Automaton (TRA) formalism, which adopts a fundamental notion of space and time that restricts expressiveness in a way that allows the specification of only reactive, spontaneous, and causal computation. Using the TRA model, unrealistic systems - possessing properties such as clairvoyance, caprice, in finite capacity, or perfect timing - cannot even be specified. We argue that this "ounce of prevention" at the specification level is likely to spare a lot of time and energy in the development cycle of responsive systems - not to mention the elimination of potential hazards that would have gone, otherwise, unnoticed. The TRA model is presented to system developers through the CLEOPATRA programming language. CLEOPATRA features a C-like imperative syntax for the description of computation, which makes it easier to incorporate in applications already using C. It is event-driven, and thus appropriate for embedded process control applications. It is object-oriented and compositional, thus advocating modularity and reusability. CLEOPATRA is semantically sound; its objects can be transformed, mechanically and unambiguously, into formal TRA automata for verification purposes, which can be pursued using model-checking or theorem proving techniques. Since 1989, an ancestor of CLEOPATRA has been in use as a specification and simulation language for embedded time-critical robotic processes.

OS Support for Portable Bulk Synchronous Parallel Programs

Predictability -- the ability to foretell that an implementation will not violate a set of specified reliability and timeliness requirements -- is a crucial, highly desirable property of responsive embedded systems. This paper overviews a development methodology for responsive systems, which enhances predictability by eliminating potential hazards resulting from physically-unsound specifications. The backbone of our methodology is the Time-constrained Reactive Automaton (TRA) formalism, which adopts a fundamental notion of space and time that restricts expressiveness in a way that allows the specification of only reactive, spontaneous, and causal computation. Using the TRA model, unrealistic systems – possessing properties such as clairvoyance, caprice, infinite capacity, or perfect timing -- cannot even be specified. We argue that this "ounce of prevention" at the specification level is likely to spare a lot of time and energy in the development cycle of responsive systems -- not to mention the elimination of potential hazards that would have gone, otherwise, unnoticed. The TRA model is presented to system developers through the Cleopatra programming language. Cleopatra features a C-like imperative syntax for the description of computation, which makes it easier to incorporate in applications already using C. It is event-driven, and thus appropriate for embedded process control applications. It is object-oriented and compositional, thus advocating modularity and reusability. Cleopatra is semantically sound; its objects can be transformed, mechanically and unambiguously, into formal TRA automata for verification purposes, which can be pursued using model-checking or theorem proving techniques. Since 1989, an ancestor of Cleopatra has been in use as a specification and simulation language for embedded time-critical robotic processes.

A New Version of Toom's Proof

There are several proofs now for the stability of Toom's example of a two-dimensional stable cellular automaton and its application to fault-tolerant computation. Simon and Berman simplified and strengthened Toom's original proof: the present report is simplified exposition of their proof.

Ergodicity and Mixing Rate of One-Dimensional Cellular Automata

One-and two-dimensional cellular automata which are known to be fault-tolerant are very complex. On the other hand, only very simple cellular automata have actually been proven to lack fault-tolerance, i.e., to be mixing. The latter either have large noise probability ε or belong to the small family of two-state nearest-neighbor monotonic rules which includes local majority voting. For a certain simple automaton L called the soldiers rule, this problem has intrigued researchers for the last two decades since L is clearly more robust than local voting: in the absence of noise, L eliminates any finite island of perturbation from an initial configuration of all 0's or all 1's. The same holds for a 4-state monotonic variant of L, K, called two-line voting. We will prove that the probabilistic cellular automata Kε and Lε asymptotically lose all information about their initial state when subject to small, strongly biased noise. The mixing property trivially implies that the systems are ergodic. The finite-time information-retaining quality of a mixing system can be represented by its relaxation time Relax(⋅), which measures the time before the onset of significant information loss. This is known to grow as (1/ε)^c for noisy local voting. The impressive error-correction ability of L has prompted some researchers to conjecture that Relax(Lε) = 2^(c/ε). We prove the tight bound 2^(c1log^21/ε) ＜ Relax(Lε) ＜ 2^(c2log^21/ε) for a biased error model. The same holds for Kε. Moreover, the lower bound is independent of the bias assumption. The strong bias assumption makes it possible to apply sparsity/renormalization techniques, the main tools of our investigation, used earlier in the opposite context of proving fault-tolerance.

Reliable Cellular Automata with Self-Organization

In a probabilistic cellular automaton in which all local transitions have positive probability, the problem of keeping a bit of information for more than a constant number of steps is nontrivial, even in an infinite automaton. Still, there is a solution in 2 dimensions, and this solution can be used to construct a simple 3-dimensional discrete-time universal fault-tolerant cellular automaton. This technique does not help much to solve the following problems: remembering a bit of information in 1 dimension; computing in dimensions lower than 3; computing in any dimension with non-synchronized transitions. Our more complex technique organizes the cells in blocks that perform a reliable simulation of a second (generalized) cellular automaton. The cells of the latter automaton are also organized in blocks, simulating even more reliably a third automaton, etc. Since all this (a possibly infinite hierarchy) is organized in "software", it must be under repair all the time from damage caused by errors. A large part of the problem is essentially self-stabilization recovering from a mess of arbitrary-size and content caused by the faults. The present paper constructs an asynchronous one-dimensional fault-tolerant cellular automaton, with the further feature of "self-organization". The latter means that unless a large amount of input information must be given, the initial configuration can be chosen to be periodical with a small period.

An intelligent clustering scheme for distributed intrusion detection in vehicular cloud computing

In recent years, vehicular cloud computing (VCC) has emerged as a new technology which is being used in wide range of applications in the area of multimedia-based healthcare applications. In VCC, vehicles act as the intelligent machines which can be used to collect and transfer the healthcare data to the local, or global sites for storage, and computation purposes, as vehicles are having comparatively limited storage and computation power for handling the multimedia files. However, due to the dynamic changes in topology, and lack of centralized monitoring points, this information can be altered, or misused. These security breaches can result in disastrous consequences such as-loss of life or financial frauds. Therefore, to address these issues, a learning automata-assisted distributive intrusion detection system is designed based on clustering. Although there exist a number of applications where the proposed scheme can be applied but, we have taken multimedia-based healthcare application for illustration of the proposed scheme. In the proposed scheme, learning automata (LA) are assumed to be stationed on the vehicles which take clustering decisions intelligently and select one of the members of the group as a cluster-head. The cluster-heads then assist in efficient storage and dissemination of information through a cloud-based infrastructure. To secure the proposed scheme from malicious activities, standard cryptographic technique is used in which the auotmaton learns from the environment and takes adaptive decisions for identification of any malicious activity in the network. A reward and penalty is given by the stochastic environment where an automaton performs its actions so that it updates its action probability vector after getting the reinforcement signal from the environment. The proposed scheme was evaluated using extensive simulations on ns-2 with SUMO. The results obtained indicate that the proposed scheme yields an improvement of 10 % in detection rate of malicious nodes when compared with the existing schemes.

Husserl's approach to transcendental intersubjectivity

It is our intention in the course of the development of this thesis to give an account of how intersubjectivity is "eidetically" constituted by means of the application of the phenomenological reduction to our experience in the context of the thought of Edmund Husserl; contrasted with various representative thinkers in what H. Spiegelberg refers to as "the wider scene" of phenomenology. That is to say, we intend to show those structures of both consciousness and the relation which man has to the world which present themselves as the generic conditions for the possibility of overcoming our "radical sol itude" in order that we may gain access to the mental 1 ife of an Other as other human subject. It is clear that in order for us to give expression to these accounts in a coherent manner, along with their relative merits, it will be necessary to develop the common features of any phenomenological theory of consdousness whatever. Therefore, our preliminary inquiry, subordinate to the larger theme, shall be into some of the epistemological results of the application of the phenomenological method used to develop a transcendental theory of consciousness. Inherent in this will be the deliniation of the exigency for making this an lIintentional ll theory. We will then be able to see how itis possible to overcome transcendentally the Other as an object merely given among other merely given objects, and further, how this other is constituted specifically as other ego. The problem of transcendental intersubjectivity and its constitution in experience can be viewed as one of the most compelling, if not the most polemical of issues in phenomenology. To be sure, right from the beginning we are forced to ask a number of questions regarding Husserl's responses to the problem within the context of the methodological genesis of the Cartesian Meditations, and The Crisis of European Sciences and Transcendental Phenomenology. This we do in order to set the stage for amplification. First, we ask, has Husserl lived up to his goal, in this connexion, of an apodictic result? We recall that in his Logos article of 1911 he adminished that previous philosophy does not have at its disposal a merely incomplete and, in particular instances, imperfect doctrinal system; it simply has none whatever. Each and every question is herein controverted, each position is a matter of individual conviction, of the interpretation given byaschool, of a "point of view". 1. Moreover in the same article he writes that his goal is a philosophical system of doctrine that, after the gigantic preparatory work. of generations, really be- . gins from the ground up with a foundation free from doubt and rises up like any skilful construction, wherein stone is set upon store, each as solid as the other, in accord with directive insights. 2. Reflecting upon the fact that he foresaw "preparatory work of generations", we perhaps should not expect that he would claim that his was the last word on the matter of intersubjectivity. Indeed, with 2. 'Edmund Husserl, lIPhilosophy as a Rigorous Science" in Phenomenology and theCrisis6fPhilosophy, trans". with an introduction by Quentin Lauer (New York.: Harper & Row, 1965) pp. 74 .. 5. 2Ibid . pp. 75 .. 6. 3. the relatively small amount of published material by Husserl on the subject we can assume that he himself was not entirely satisfied with his solution. The second question we have is that if the transcendental reduction is to yield the generic and apodictic structures of the relationship of consciousness to its various possible objects, how far can we extend this particular constitutive synthetic function to intersubjectivity where the objects must of necessity always remain delitescent? To be sure, the type of 'object' here to be considered is unlike any other which might appear in the perceptual field. What kind of indubitable evidence will convince us that the characteristic which we label "alter-ego" and which we attribute to an object which appears to resemble another body which we have never, and can never see the whole of (namely, our own bodies), is nothing more than a cleverly contrived automaton? What;s the nature of this peculiar intentional function which enables us to say "you think just as I do"? If phenomenology is to take such great pains to reduce the takenfor- granted, lived, everyday world to an immanent world of pure presentation, we must ask the mode of presentation for transcendent sub .. jectivities. And in the end, we must ask if Husserl's argument is not reducible to a case (however special) of reasoning by analogy, and if so, tf this type of reasoning is not so removed from that from whtch the analogy is made that it would render all transcendental intersubjective understandtng impos'sible? 2. HistoticalandEidetic Priority: The Necessity of Abstraction 4. The problem is not a simple one. What is being sought are the conditions for the poss ibili:ty of experi encing other subjects. More precisely, the question of the possibility of intersubjectivity is the question of the essence of intersubjectivity. What we are seeking is the absolute route from one solitude to another. Inherent in this programme is the ultimate discovery of the meaning of community. That this route needs be lIabstract" requires some explanation. It requires little explanation that we agree with Husserl in the aim of fixing the goal of philosophy on apodictic, unquestionable results. This means that we seek a philosophical approach which is, though, not necessarily free from assumptions, one which examines and makes explicit all assumptions in a thorough manner. It would be helpful at this point to distinguish between lIeidetic ll priority, and JlhistoricallJpriority in order to shed some light on the value, in this context, of an abstraction.3 It is true that intersubjectivity is mundanely an accomplished fact, there havi.ng been so many mi.llions of years for humans to beIt eve in the exi s tence of one another I s abili ty to think as they do. But what we seek is not to study how this proceeded historically, but 3Cf• Maurice Natanson;·TheJburne in 'Self, a Stud in Philoso h and Social Role (Santa Cruz, U. of California Press, 1970 . rather the logical, nay, "psychological" conditions under which this is possible at all. It is therefore irrelevant to the exigesis of this monograph whether or not anyone should shrug his shoulders and mumble IIwhy worry about it, it is always already engaged". By way of an explanation of the value of logical priority, we can find an analogy in the case of language. Certainly the language 5. in a spoken or written form predates the formulation of the appropriate grammar. However, this grammar has a logical priority insofar as it lays out the conditions from which that language exhibits coherence. The act of formulating the grammar is a case of abstraction. The abstraction towards the discovery of the conditions for the poss; bi 1 ity of any experiencing whatever, for which intersubjective experience is a definite case, manifests itself as a sort of "grammar". This "grammar" is like the basic grammar of a language in the sense that these "rulesil are the ~ priori conditions for the possibility of that experience. There is, we shall say, an "eidetic priority", or a generic condition which is the logical antecedent to the taken-forgranted object of experience. In the case of intersubjectivity we readily grant that one may mundanely be aware of fellow-men as fellowmen, but in order to discover how that awareness is possible it is necessary to abstract from the mundane, believed-in experience. This process of abstraction is the paramount issue; the first step, in the search for an apodictic basis for social relations. How then is this abstraction to be accomplished? What is the nature of an abstraction which would permit us an Archimedean point, absolutely grounded, from which we may proceed? The answer can be discovered in an examination of Descartes in the light of Husserl's criticism. 3. The Impulse for Scientific Philosophy. The Method to which it Gives Rise. 6. Foremost in our inquiry is the discovery of a method appropriate to the discovery of our grounding point. For the purposes of our investigations, i.e., that of attempting to give a phenomenological view of the problem of intersubjectivity, it would appear to be of cardinal importance to trace the attempt of philosophy predating Husserl, particularly in the philosophy of Descartes, at founding a truly IIscientific ll philosophy. Paramount in this connexion would be the impulse in the Modern period, as the result of more or less recent discoveries in the natural sciences, to found philosophy upon scientific and mathematical principles. This impulse was intended to culminate in an all-encompassing knowledge which might extend to every realm of possible thought, viz., the universal science ot IIMathexis Universalis ll •4 This was a central issue for Descartes, whose conception of a universal science would include all the possible sciences of man. This inclination towards a science upon which all other sciences might be based waS not to be belittled by Husserl, who would appropriate 4This term, according to Jacab Klein, was first used by Barocius, the translator of Proclus into Latin, to designate the highest mathematical discipline. . 7. it himself in hopes of establishing, for the very first time, philosophy as a "rigorous science". It bears emphasizing that this in fact was the drive for the hardening of the foundations of philosophy, the link between the philosophical projects of Husserl and those of the philosophers of the modern period. Indeed, Husserl owes Descartes quite a debt for indicating the starting place from which to attempt a radical, presupositionless, and therefore scientific philosophy, in order not to begin philosophy anew, but rather for the first time.5 The aim of philosophy for Husserl is the search for apodictic, radical certitude. However while he attempted to locate in experience the type of necessity which is found in mathematics, he wished this necessity to be a function of our life in the world, as opposed to the definition and postulation of an axiomatic method as might be found in the unexpurgated attempts to found philosophy in Descartes. Beyond the necessity which is involved in experiencing the world, Husserl was searching for the certainty of roots, of the conditi'ons which underl ie experience and render it pOssible. Descartes believed that hi~ MeditatiOns had uncovered an absolute ground for knowledge, one founded upon the ineluctable givenness of thinking which is present even when one doubts thinking. Husserl, in acknowledging this procedure is certainly Cartesian, but moves, despite this debt to Descartes, far beyond Cartesian philosophy i.n his phenomenology (and in many respects, closer to home). 5Cf. Husserl, Philosophy as a Rigorous Science, pp. 74ff. 8 But wherein lies this Cartesian jumping off point by which we may vivify our theme? Descartes, through inner reflection, saw that all of his convictions and beliefs about the world were coloured in one way or another by prejudice: ... at the end I feel constrained to reply that there is nothing in a all that I formerly believed to be true, of which I cannot in some measure doubt, and that not merely through want of thought or through levity, but for reasons which are very powerful and maturely considered; so that henceforth I ought not the less carefully to refrain from giving credence to these opinions than to that which is manifestly false, if I desire to arrive at any certainty (in the sciences). 6 Doubts arise regardless of the nature of belief - one can never completely believe what one believes. Therefore, in order to establish absolutely grounded knowledge, which may serve as the basis fora "universal Science", one must use a method by which one may purge oneself of all doubts and thereby gain some radically indubitable insight into knowledge. Such a method, gescartes found, was that, as indicated above by hi,s own words, of II radical doubt" which "forbids in advance any judgemental use of (previous convictions and) which forbids taking any position with regard to their val idi'ty. ,,7 This is the method of the "sceptical epoche ll , the method of doubting all which had heretofor 6Descartes,Meditations on First Philosophy, first Med., (Libera 1 Arts Press, New York, 1954) trans. by L. LaFl eur. pp. 10. 7Husserl ,CrisiS of Eliroeari SCiences and Trariscendental Phenomenology, (Northwestern U. Press, Evanston, 1 7 ,p. 76. 9. been considered as belonging to the world, including the world itself. What then is left over? Via the process of a thorough and all-inclusive doubting, Descartes discovers that the ego which performs the epoche, or "reduction", is excluded from these things which can be doubted, and, in principle provides something which is beyond doubt. Consequently this ego provides an absolute and apodictic starting point for founding scientific philosophy. By way of this abstention. of bel ief, Desca'rtes managed to reduce the worl d of everyday 1 ife as bel ieved in, to mere 'phenomena', components of the rescogitans:. Thus:, having discovered his Archimedean point, the existence of the ego without question, he proceeds to deduce the 'rest' of the world with the aid of innate ideas and the veracity of God. In both Husserl and Descartes the compelling problem is that of establ ishing a scientific, apodictic phi'losophy based upon presuppos itionless groundwork .. Husserl, in thi.s regard, levels the charge at Descartes that the engagement of his method was not complete, such that hi.S: starting place was not indeed presupositionless, and that the validity of both causality and deductive methods were not called into question i.'n the performance of theepoche. In this way it is easy for an absolute evidence to make sure of the ego as: a first, "absolute, indubitablyexisting tag~end of the worldll , and it is then only a matter of inferring the absolute subs.tance and the other substances which belon.g to the world, along with my own mental substance, using a logically val i d deductive procedure. 8 8Husserl, E.;' Cartesian 'Meditation;, trans. Dorion Cairns (Martinus Nijhoff, The Hague, 1970), p. 24 ff.

The career of the missed encounter in classic american literature

Cette dissertation explore la carrière de la rencontre manquée Lacanienne dans la littérature canonique américaine du dix-neuvième siècle à travers le prisme de la psychanalyse, la déconstruction, le postmodernisme et le postcolonialisme. Je me concentre particulièrement sur La Lettre Écarlate de Hawthorne et Moby-Dick de Melville, en montrant comment ils sont investis dans l'économie narrative de la rencontre manquée, l'économie de ce qui est au-delà de la symbolisation et l'assimilation. L’introduction examine les contours et les détours historiques, philosophiques et théoriques du concept de la rencontre manquée. Cette dissertation a donc deux objectifs: d'une part, elle tente d'examiner le statut et la fonction de la rencontre manquée dans la littérature américaine du dix-neuvième siècle, et d’autre part, elle explore comment la théorisation de la rencontre manquée pourrait nous aider à aller au-delà de la théorisation binaire qui caractérise les scènes géopolitiques actuelles. Mon premier chapitre sur La Lettre Écarlate de Hawthorne, tente de tracer la carrière du signifiant comme une navette entre l'archive et l'avenir, entre le sujet et l'objet, entre le signifiant et le signifié. Le but de ce chapitre est de rendre compte de la temporalité du signifiant et la temporalité de la subjectivité et d’expliquer comment ils répondent à la temporalité du tuché. En explorant la dimension crypto-temporelle de la rencontre manquée, ce chapitre étudie l'excès de cryptes par la poétique (principalement prosopopée, anasémie, et les tropes d'exhumation). Le deuxième chapitre élabore sur les contours de la rencontre manquée. En adoptant des approches psychanalytiques et déconstructives, ce chapitre négocie la temporalité de la rencontre manquée (la temporalité de l'automaton et de la répétition). En explorant la temporalité narrative (prolepse et analepse) conjointement à la psycho-poétique du double, ce chapitre essaie de dévoiler les vicissitudes de la mélancolie et la “dépression narcissique” dans Moby-Dick (en particulier la répétition d'Achab lors de sa rencontre originelle dénarrée ou jamais racontée avec le cachalot blanc et sa position mélancolique par rapport à l'objet qu'il a perdu). En exposant la nature du trauma comme une rencontre manquée, dont les résidus se manifestent symptomatiquement par la répétition (et le doublement), ce chapitre explique le glissement de la lettre (par l'entremise du supplément et de la différance). Le troisième chapitre élargit la portée de la rencontre manquée pour inclure les Autres de l'Amérique. Le but principal de ce chapitre est d'évaluer les investitures politiques, culturelles, imaginaires et libidinales de la rencontre manquée dans le Réel, le Symbolique nationale des États-Unis et la réalité géopolitique actuelle. Il traite également de la relation ambiguë entre la jouissance et le Symbolique: la manière dont la jouissance anime et régit le Symbolique tout en confondant la distinction entre le Réel et la réalité et en protégeant ses manœuvres excessives.

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.

A study on semigroup action on fuzzy subsets, inverse fuzzy automata and related topics

This thesis comprises five chapters including the introductory chapter. This includes a brief introduction and basic definitions of fuzzy set theory and its applications, semigroup action on sets, finite semigroup theory, its application in automata theory along with references which are used in this thesis. In the second chapter we defined an S-fuzzy subset of X with the extension of the notion of semigroup action of S on X to semigroup action of S on to a fuzzy subset of X using Zadeh's maximal extension principal and proved some results based on this. We also defined an S-fuzzy morphism between two S-fuzzy subsets of X and they together form a category S FSETX. Some general properties and special objects in this category are studied and finally proved that S SET and S FSET are categorically equivalent. Further we tried to generalize this concept to the action of a fuzzy semigroup on fuzzy subsets. As an application, using the above idea, we convert a _nite state automaton to a finite fuzzy state automaton. A classical automata determine whether a word is accepted by the automaton where as a _nite fuzzy state automaton determine the degree of acceptance of the word by the automaton. 1.5. Summary of the Thesis 17 In the third chapter we de_ne regular and inverse fuzzy automata, its construction, and prove that the corresponding transition monoids are regular and inverse monoids respectively. The languages accepted by an inverse fuzzy automata is an inverse fuzzy language and we give a characterization of an inverse fuzzy language. We study some of its algebraic properties and prove that the collection IFL on an alphabet does not form a variety since it is not closed under inverse homomorphic images. We also prove some results based on the fact that a semigroup is inverse if and only if idempotents commute and every L-class or R-class contains a unique idempotent. Fourth chapter includes a study of the structure of the automorphism group of a deterministic faithful inverse fuzzy automaton and prove that it is equal to a subgroup of the inverse monoid of all one-one partial fuzzy transformations on the state set. In the fifth chapter we define min-weighted and max-weighted power automata study some of its algebraic properties and prove that a fuzzy automaton and the fuzzy power automata associated with it have the same transition monoids. The thesis ends with a conclusion of the work done and the scope of further study.

Restarting automata with restricted utilization of auxiliary symbols

The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

Shrinking restarting automata

Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.