Operations and language generating devices suggested by the genome evolution
Language-theoretic problems arising from the genome evolution discussed in series of papers of the authors, Proc. 2nd Pacific Symp. on Biocomputing, World Scientific, Singapore, 1997, pp. 97-108; Bioinformatics, Lect. Notes Comput. Sci. 1278, 199-209; BioSystems 43, 169-177 (1997); Jewels are Forever, Springer, Berlin, 1999, pp. 171-181) are presented in a uniform way. The main emphasis is on the operations of inversion, transposition, duplication and deletion suggested by the genome evolution. Basic problems concerning these operations and their iterated versions are settled. A generative device (evolutionary grammar) based on these operations is investigated from different points of view (computational power, decidability problems, descriptional complexity). ``Adult languages (sets of stable strings) of such evolutionary grammars possess a surprising generative power.
- Bounded Regular Sets
- scientific article; zbMATH DE number 3767067 (Why is no real title available?)
- scientific article; zbMATH DE number 50943 (Why is no real title available?)
- scientific article; zbMATH DE number 3543644 (Why is no real title available?)
- scientific article; zbMATH DE number 3569855 (Why is no real title available?)
- scientific article; zbMATH DE number 1236223 (Why is no real title available?)
- scientific article; zbMATH DE number 1337734 (Why is no real title available?)
- scientific article; zbMATH DE number 1355000 (Why is no real title available?)
- scientific article; zbMATH DE number 1355188 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 1406009 (Why is no real title available?)
- scientific article; zbMATH DE number 1407503 (Why is no real title available?)
- scientific article; zbMATH DE number 1408343 (Why is no real title available?)
- Normal forms for phrase-structure grammars
- On the irregularity of the duplication closure
- On the regularity of languages generated by context-free evolutionary grammars
- Pure grammars
- Pure grammars and pure languages†
- String variable grammar: A logic grammar formalism for the biological language of DNA
- Closure and decidability properties of some language classes with respect to ciliate bio-operations.
- Evolutionary systems: A language generating device inspired by evolving communities of cells
- Pseudo-inversion: closure properties and decidability
- Bound-decreasing duplication system
- Duplications and pseudo-duplications
- Notes on dual concatenation
- Duplication in DNA Sequences
- Ambiguous grammars and the chemical transactions of life
- scientific article; zbMATH DE number 1337734 (Why is no real title available?)
- scientific article; zbMATH DE number 1355188 (Why is no real title available?)
- scientific article; zbMATH DE number 1408343 (Why is no real title available?)
- Non-overlapping inversion on strings and languages
- Gaining Power by Input Operations: Finite Automata and Beyond
- LANGUAGE FAMILIES DEFINED BY A CILIATE BIO-OPERATION: HIERARCHIES AND DECISION PROBLEMS
- Watson-Crick jumping finite automata
- Graph grammars with string-regulated rewriting
- State complexity of inversion operations
This page was built for publication: Operations and language generating devices suggested by the genome evolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958327)
