1,720,962 research outputs found
Observation of string-rewriting systems
No full textModels of computation in theoretical computer science very frequently consist of a device performing some type of process, like a Turing machine and its computation or a grammar and its derivation. After the process halts, only some final output is regarded as the result. In adding an observer to such a device, one can obtain a protocol of the entire process and then use this as the result of the computation. In several recent articles this approach has proved to often exceed greatly the power of the observed system. Here we apply this architecture to string-rewriting systems. They receive a string as input, and a combination of observer and decider then determines whether this string is accepted. This decision is based only on the rewriting process performed. First we determine the power of painter, context-free, and inverse context-free rewriting systems in terms of McNaughton languages. Then these are investigated as components of rewriting/observer systems, and we obtain characterizations of the classes of context-sensitive and recursively enumerable languages. Finally we investigate some limitations, i.e. characterize some systems, where observation does not increase power
Evolution and Observation: A Non-standard Way to Accept Formal Languages
No full textIt is a very common procedure in biology to observe the progress of an experiment and regard the result of this observation as the final outcome. Inspired by this, a new approach for generating formal languages, called evolution/observation, has been introduced [6]. In the current work we consider evolution/observation as a new strategy also for accepting languages: a word is accepted, if the (observed) evolution of a certain system starting from this input follows a regular pattern. We obtain the following result: checking if the (observed) evolution of a context-free system follows a regular pattern is enough to accept every recursively enumerable languages. On the other hand, if we observe the evolution of systems using very simple rules (of the kind a → b), then it is possible to accept exactly the class of context-sensitive languages. © Springer-Verlag Berlin Heidelberg 2005
Evolution and observation—a non-standard way to generate formal languages
No full textAbstractIn biology and chemistry a standard proceeding is to conduct an experiment, observe its progress, and then take the result of this observation as the final output. Inspired by this, we have introduced P/O systems (A. Alhazov, C. Martı́n-Vide, Gh. Păun, Pre-Proc. of the Workshop on Membrane Computing 2003, Tarrragona, Spain; http://pizarro.fll.urv.es/continguts/linguistica/proyecto/reports/wmc03.html), where languages are generated by multiset automata that observe the evolution of membrane systems.Now we apply this approach also to more classical devices of formal language theory. Namely, we use finite automata observing the derivations of grammars or of Lindenmayer systems. We define several modes of operation for grammar/observer systems. In two of these modes a context-free grammar (or even a locally commutative context-free grammar) with a finite automaton as observer suffices to generate any recursively enumerable language. In a third case, we obtain a class of languages between the context-free and context-sensitive ones
Computing by observing: Simple systems and simple observers
No full textAbstractWe survey and extend the work on the paradigm called “computing by observing”. Its central feature is that one considers the behavior of an evolving system as the result of a computation. To this purpose an external observer records this behavior. In this way, several computational trade-offs between the observer and the observed system can be determined. It has turned out that the observed behavior of computationally simple systems can be very complex, when an appropriate observer is used. For example, a restricted version of context-free grammars with regular observers suffices to obtain computational completeness. As a second instantiation presented here, we apply an observer to sticker systems, an abstract model of DNA computing. Finally, we introduce and investigate the case where the observers can read only one measure of the observed system (e.g., mass or temperature), modeling in this way the limitations in the observation of real physical systems. Finally, a research perspective on the topic is presented
Evolution and Observation - a New Way to Look at Membrane Systems
No full textAn architecture for investigating the dynamical behaviour of biological systems is proposed by using the concepts of \behaviour" and \observer". The behaviour of a biological system is the sequence of states traversed as time passes; the observer is a device translating this behaviour into a readable output
DNA splicing: computing by observing
Full text linkMotivated by several techniques for observing molecular processes in real-time we introduce a computing device that stresses the role of the observer in biological computations and that is based on the observed behavior of a splicing system. The basic idea is to introduce a marked DNA strand into a test tube with other DNA strands and restriction enzymes. Under the action of these enzymes the DNA starts to splice. An external observer monitors and registers the evolution of the marked DNA strand. The input marked DNA strand is then accepted if its observed evolution follows a certain expected pattern. We prove that using simple observers (finite automata), applied on finite splicing systems (finite set of rules and finite set of axioms), the class of recursively enumerable languages can be recognized
Recognizing DNA Splicing
No full textMotivated by recent techniques developed for observing evolutionary dynamics of a single DNA molecule, we introduce a formal model for accepting an observed behavior of a splicing system. The main idea is to input a marked DNA strand into a test tube together with certain restriction enzymes and, possibly, with other DNA strands. Under the action of the enzymes, the marked DNA strand starts to evolve by splicing with other DNA strands. The evolution of the marked DNA strand is "observed" by an outside observer and the input DNA strand is "accepted" if its (observed) evolution follows a certain expected pattern. We prove that using finite splicing system (finite set of rules and finite set of axioms), universal computation is attainable with simple observing and accepting devices made of finite state automata. © Springer-Verlag Berlin Heidelberg 2006
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
