Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2012 | Buch

Peptide Computers Kapitel lesen Erstes Kapitel lesen

Languages Alive

Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday

herausgegeben von: Henning Bordihn, Martin Kutrib, Bianca Truthe

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This festschrift volume, published in honor of Jürgen Dassow on the occasion of his 65th birthday, contains 19 contributions by leading researchers, colleagues, and friends. Covering topics on picture languages, cooperating distributed systems of automata, quantum automata, grammar systems, online computation, word equations, biologically motivated formal systems, controlled derivations, descriptional complexity, as well as 'classical' topics of automata and language theory, the articles presented span the range of the scientific work of Jürgen Dassow.

Inhaltsverzeichnis

Frontmatter
Peptide Computers
Abstract
A peptide computer is a formal model for computations based on peptide-antibody interactions. We provide a rigorous detailed formal model and prove that this model leads to a well-defined computational behaviour. We review existing results concerning the power and limitations of peptide computers and the types of non-determinism arising in such computers on the basis of this formal model.
M. Sakthi Balan, Helmut Jürgensen
On the Power of Randomness versus Advice in Online Computation
Abstract
The recently introduced model of advice complexity of online problems tries to achieve a fine-grained analysis of the hardness of online problems by asking how many bits of advice about the still unknown parts of the input an oracle has to provide for an online algorithm to guarantee a specific competitive ratio. Until now, only deterministic online algorithms with advice were considered in the literature. In this paper, we consider, for the first time, online algorithms having access to both random bits and advice bits. For this, we introduce the online problem (n,k)-Boxes: Given a number of n closed boxes, an adversary hides \(k<\sqrt{n}\) items, each of unit value, within k consecutive boxes. The goal is to open exactly k boxes and gain as many items as possible.
In the classical online setting without advice, we show that, if k(k + 1) ≤ n, any deterministic algorithm is not competitive, because the adversary can ensure that not a single item is found. However, randomization drastically increases the gain in expectation. More precisely, we prove that the expected gain is in the order of k3/n and show that this bound is tight up to some constant factor. A crucial result of our analysis is the proof of the existence of two thresholds for the amount of random bits used for solving (n,k)-Boxes. If the amount of random bits is below the first threshold, randomization does not help at all. If, on the other hand, the amount of randomness is above the second threshold of about logn − 2logk random bits, then any additional random bit does not help to improve the gain.
As our main result, we analyze the advice complexity of the boxes problem both for deterministic and randomized online algorithms and give a tight trade-off between the number of random bits and advice bits needed for achieving a specific competitive ratio.
Hans-Joachim Böckenhauer, Juraj Hromkovič, Dennis Komm, Richard Královič, Peter Rossmanith
Relevance of Entities in Reaction Systems
Abstract
Reaction systems are a model for the investigation of processes carried out by biochemical reactions in living cells. A reaction system consists of a set of reactions which transform a current system’s state (a set of entities) into the successor state. In this paper we investigate which entities are actually relevant from the point of view of generating dynamic processes through such state transformations.
Andrzej Ehrenfeucht, Jetty Kleijn, Maciej Koutny, Grzegorz Rozenberg
Generalized Random Context Picture Grammars: The State of the Art
Abstract
Generalized random context picture grammars (grcpgs) are a method of syntactic picture generation. The terminals are subsets of the Euclidean plane and the replacement of variables involves the building of functions that will eventually be applied to terminals. Context is used to permit or forbid production rules.
Iterated function systems (IFSs) and their generalization, mutually recursive function systems (MRFSs), are among the best-known methods for constructing fractals. In earlier work it was shown that any picture sequence generated by an IFS or MRFS can be generated by a grcpg. Moreover, it was shown that grcpgs can generate a wider range of pictures than IFSs or MRFSs.
In this essay we give a summary of the above mentioned results. We then consider language-restricted iterated function systems (LRIFSs), a method of picture generation where a language controls which functions of an IFS are applied. We first show that LRIFSs are more powerful than IFSs. Then we show that any picture produced by an LRIFS where the restricting language is regular, can be approximated by a grcpg.
Sigrid Ewert, Max Rabkin
Cooperating Distributed Tree Automata
Abstract
We propose a study on cooperating distributed tree automata, proving in particular characterizations of the yields of such automata systems.
Henning Fernau
A Note on Combined Derivation Modes for Cooperating Distributed Grammar Systems
Abstract
We investigate the generative power of cooperating distributed grammar systems (CDGS) with context-free rules working in cut-f-mode of derivation, when f is a full-competence mode in combination with another derivation mode, combined sf-mode, for short. Cut-modes were introduced in [Bordihn, Holzer: Cooperating distributed grammar systems as models of distributed problem solving, Fund. Inform. 76, 2007] in order to model distributed problem solving by CDGSs, and combined sf-modes were recently investigated in [Bordihn, Holzer: A note on cooperating distributed grammar systems working in combined modes. Inform. Process. Lett. 108, 2008]. While cut-f-modes were investigated for the classical CDGS derivation modes and moreover also for combined t-modes, the generative capacity for cut-modes based on combined sf-modes was left open in the literature. This paper closes this gap.
Markus Holzer
Equations in the Partial Semigroup of Words with Overlapping Products
Abstract
We consider an overlapping product of words as a partial operation where the product of two words is defined when the former ends with the same letter as the latter starts, and in this case the product is obtained by merging these two occurrences of letters, for example aba ∙ ab = abab. Some basic results on equations of words are established by reducing them to corresponding results of ordinary word equations.
Mari Huova, Juhani Karhumäki
On CD-Systems of Stateless Deterministic Two-Phase RR(1)-Automata
Abstract
We study stateless deterministic two-phase RR-automata of window size one: stl-det-2-RR(1)-automata. While general deterministic RR-automata of window size one characterize the regular languages, it turns out that the class of languages accepted by the stateless two-phase variants is subregular. Therefore we combine stl-det-2-RR(1)-automata into computationally stronger cooperating distributed systems, obtaining the stl-det-local-CD-2-RR(1)-systems. By limiting their inherent nondeterminism, two further variants are derived. The relations between the different classes and some well-known language families are investigated, and it is shown that the classes defined here form a finite hierarchy whose levels are incomparable to several well-known language families. Further, closure properties and decision problems are studied for these classes.
Martin Kutrib, Friedrich Otto
The Boolean Formula Value Problem as Formal Language
Abstract
The Boolean formula value problem asks for the Boolean output value of a given input formula. We code it as a formal language \(\ensuremath{{\cal D_+}}\subset\{a,b\}^*\). \({\cal D_+}\) is a nonregular, visibly pushdown language. We give automata for \({\cal D_+}\) which enable us to derive some of its syntactic equations. It is unknown whether the given list of equations is complete. Using these equations some algebraic properties of the syntactic monoid of \({\cal D_+}\) are sketched.
Klaus-Jörn Lange
Hairpin Lengthening and Shortening of Regular Languages
Abstract
We consider here two formal operations on words inspired by the DNA biochemistry: hairpin lengthening introduced in [15] and its inverse called hairpin shortening. We study the closure of the class of regular languages under the non-iterated and iterated variants of the two operations. The main results are: although any finite number of applications of the hairpin lengthening to a regular language may lead to non-regular languages, the iterated hairpin lengthening of a regular language is always regular. As far as the hairpin shortening operation is concerned, the class of regular languages is closed under bounded and unbounded iterated hairpin shortening.
Florin Manea, Robert Mercas, Victor Mitrana
One-Sided Random Context Grammars with Leftmost Derivations
Abstract
In this paper, we study the generative power of one-sided random context grammars working in a leftmost way. More specifically, by analogy with the three well-known types of leftmost derivations in regulated grammars, we introduce three types of leftmost derivations to one-sided random context grammars and prove the following three results. (I) One-sided random context grammars with type-1 leftmost derivations characterize the family of context-free languages. (II) One-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of recursively enumerable languages. (III) Propagating one-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of context-sensitive languages. In the conclusion, the generative power of random context grammars and one-sided random context grammars with leftmost derivations is compared.
Alexander Meduna, Petr Zemek
Earley’s Parsing Algorithm and k-Petri Net Controlled Grammars
Abstract
In this paper we modify Earley’s parsing algorithm to parse words generated by Petri net controlled grammars. Adding a vector which corresponds to a marking of a Petri net to Earley’s algorithm, it is shown that languages generated by a subclass of k-Petri net controlled grammars (introduced by J. Dassow and S. Turaev) are parsed in polynomial time of the length of a word.
Taishin Y. Nishida
Descriptional Complexity of Input-Driven Pushdown Automata
Abstract
It is known that a nondeterministic input-driven pushdown automaton (IDPDA) can be determinized. Alur and Madhusudan (“Adding nesting structure to words”, J.ACM 56(3), 2009) showed that a deterministic IDPDA simulating a nondeterministic IDPDA with n states and stack symbols may need, in the worst case, \(2^{\Omega(n^2)}\) states. In their construction, the equivalent deterministic IDPDA does, in fact, not need to use the stack. This paper considers the size blow-up of determinization in more detail, and gives a lower bound construction, that is tight within a multiplicative constant, with respect to the size of the nondeterministic automaton both for the number of states and the number of stack symbols. The paper also surveys the recent results on operational state complexity of IDPDAs, and on the cost of converting a nondeterministic automaton to an unambiguous one, and an unambiguous automaton to a deterministic one.
Alexander Okhotin, Xiaoxue Piao, Kai Salomaa
Towards “Fypercomputations” (in Membrane Computing)
Abstract
Looking for ideas which would lead to computing devices able to compute “beyond the Turing barrier” is already a well established research area of computing theory; such devices are said to be able of doing hypercomputations. It is also a dream and a concern of computability to speed-up computing devices; we propose here a name for the case when this leads to polynomial solutions to problems known to be (at least) NP-complete: fypercomputing – with the initial F coming from “fast”.
In short: fypercomputing means going polynomially beyond NP.
The aim of these notes is to briefly discuss the existing ideas in membrane computing which lead to fypercomputations and to imagine new ones, some of them at the level of speculations, subject for further investigation.
Gheorghe Păun
Undecidability of State Complexities Using Mirror Images
Abstract
We establish the undecidability of the state complexity of compositions of the operation mirror image and two other regularity-preserving operations. The undecidability of Hilbert’s Tenth Problem is not needed; the weaker Davis-Putnam-Robinson Theorem suffices for the reduction. Special attention is paid to the maximal state complexity of mirror images and the maximal deterministic state complexity of nondeterministic finite automata.
Arto Salomaa
Asymptotic Subword Complexity
Abstract
The subword complexity of an infinite word ξ is a function f(ξ,n) returning the number of finite subwords (factors, infixes) of length n of ξ. In the present paper we investigate infinite words for which the set of subwords occurring infinitely often is a regular language. Among these infinite words we characterise those which are eventually recurrent.
Furthermore, we derive some results comparing the asymptotics of f(ξ,n) to the information content of sets of finite or infinite words related to ξ. Finally we give a simplified proof of Theorem 6 of [18].
Ludwig Staiger
On Grammars Controlled by Parikh Vectors
Abstract
We suggest a concept of grammars with controlled derivations where the Parikh vectors of all intermediate sentential forms have to be from a given restricting set. For several classes of restricting sets, we investigate set-theoretic and closure properties of the corresponding language families.
Ralf Stiebe
On the Nonterminal Complexity of Tree Controlled Grammars
Abstract
A tree controlled grammar is a regulated rewriting device which can be given as a pair (G,R) where G is a context-free grammar and R is a regular set over the terminal and nonterminal alphabets of G. The language generated by the tree controlled grammar contains those words of L(G) which have a derivation tree where all the words obtained by reading the symbols labeling the nodes belonging to the different levels of the tree, from left to right, belong to the language R. The nonterminal complexity of tree controlled grammars can be given as the number of nonterminals of the context-free grammar G, and the number of nonterminals that a regular grammar needs to generate the control language R. Here we improve the currently known best upper bound on the nonterminal complexity of tree controlled grammars from seven to six, that is, we show that a context-free grammar with five nonterminals and a control language which can be generated by a grammar with one nonterminal is sufficient to generate any recursively enumerable language.
György Vaszil
One-Way Finite Automata with Quantum and Classical States
Abstract
In this paper, we introduce and explore a new model of quantum finite automata (QFA). Namely, one-way finite automata with quantum and classical states (1QCFA), a one way version of two-way finite automata with quantum and classical states (2QCFA) introduced by Ambainis and Watrous in 2002 [3]. First, we prove that coin-tossing one-way probabilistic finite automata (coin-tossing 1PFA) [23] and one-way quantum finite automata with control language (1QFACL) [6] as well as several other models of QFA, can be simulated by 1QCFA. Afterwards, we explore several closure properties for the family of languages accepted by 1QCFA. Finally, the state complexity of 1QCFA is explored and the main succinctness result is derived. Namely, for any prime m and any ε1 > 0, there exists a language L m that cannot be recognized by any measure-many one-way quantum finite automata (MM-1QFA) [12] with bounded error \(\frac{7}{9}+\epsilon_1\), and any 1PFA recognizing it has at last m states, but L m can be recognized by a 1QCFA for any error bound ε > 0 with O(logm) quantum states and 12 classical states.
Shenggen Zheng, Daowen Qiu, Lvzhou Li, Jozef Gruska
Backmatter
Metadaten
Titel
Languages Alive
herausgegeben von
Henning Bordihn
Martin Kutrib
Bianca Truthe
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-31644-9
Print ISBN
978-3-642-31643-2
DOI
https://doi.org/10.1007/978-3-642-31644-9

Premium Partner

    Bildnachweise