Closure and decidability properties of some language classes with respect to ciliate bio-operations.

DOI10.1016/S0304-3975(03)00139-7zbMath1060.68060MaRDI QIDQ1426436

Lila Kari, Mark Daley, Oscar H. Ibarra

Publication date: 14 March 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

unscrambling in ciliates

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Protein sequences, DNA sequences (92D20) Genetics and epigenetics (92D10)

Related Items (15)

The chop of languages ⋮ SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED ⋮ Families of languages defined by ciliate bio-operations ⋮ On codes defined by bio-operations ⋮ State complexity of inversion operations ⋮ Evolving schemas for streaming XML ⋮ Pseudo-inversion: closure properties and decidability ⋮ Decision problems for language equations ⋮ Gaining Power by Input Operations: Finite Automata and Beyond ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ LANGUAGE FAMILIES DEFINED BY A CILIATE BIO-OPERATION: HIERARCHIES AND DECISION PROBLEMS ⋮ REDUCTION GRAPHS FROM OVERLAP GRAPHS FOR GENE ASSEMBLY IN CILIATES ⋮ On decidability and closure properties of language classes with respect to bio-operations ⋮ INTRA-MOLECULAR TEMPLATE-GUIDED RECOMBINATION ⋮ Decidability of trajectory-based equations

Cites Work

• On some operations on strings suggested by gene assembly in ciliates
• Reversal-bounded multipushdown machines
• On language equations with invertible operations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Operations and language generating devices suggested by the genome evolution
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Closure and decidability properties of some language classes with respect to ciliate bio-operations.