Top

Natural Computing

Published in:

01-06-2016

On decidability and closure properties of language classes with respect to bio-operations

Author: Oscar H. Ibarra

Published in: Natural Computing | Issue 2/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under bio-operations such hairpin-inversion, the recently studied operation of pseudo-inversion, and other bio-operations. We also provide techniques for proving undecidability results. In particular, we give a new approach for proving the undecidability of problems for which the usual method of reduction to the undecidability of the Post Correspondence Problem seems hard to apply. Our closure and decidability results strengthen or generalize previous results.

previous article The computational capability of chemical reaction automata

next article Minimal output unstable configurations in chemical reaction networks and deciders

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Cho D-J, Han Y-S, Kang S-D, Kim H, Ko S-K, Salomaa K (2014) Pseudo-inversion on formal languages. In: Proceedings of the unconventional computation and natural computation 2014, pp 93–104

Daley M, Ibarra OH, Kari L (2003) Closure and decidability properties of some languages classes with respect to ciliate bio-operations. Theor Comput Sci 306(1–3):19–38MathSciNetCrossRefMATH

Daley M, Kari L, McQuillan I (2004) Families of languages defined by ciliate bio-operations. Theor Comput Sci 320(1):51–69MathSciNetCrossRefMATH

Deaton R, Garzon M, Murphy RC, Rose JA, Franceschetti DR, Stevens SE Jr (1996) Genetic search of reliable encodings for DNA-based computation. In: Proceedings of the 1st conference on genetic programming, pp 9–15

Garzon M, Deaton R, Nino LF, Stevens E, Wittner M (1998) Encoding genomes for DNA computing. In: Proceedings of the of 3rd annual conference on genetic programming 1998, pp 684–690

Ginsburg S (1966) The mathematical theory of context-free languages. McGraw-Hill, New YorkMATH

Gurari E, Ibarra OH (1981) The complexity of decision problems for finite-turn multicounter machines. J Comput Syst Sci 22:220–229MathSciNetCrossRefMATH

Hague M, Lin AW (2011) Model checking recursive programs with numeric data types. In: CAV 2011, pp 743–759

Hopcroft JE, Ullman JD (1978) Introduction to automata, languages and computation. Addison-Wesley, ReadingMATH

Hussini S, Kari L, Konstantinidis S (2002) Coding properties of DNA languages. In: Proceeding of the 8th international meeting on DNA computing, pp 57–69

Ibarra OH (1978) Reversal-bounded multicounter machines and their decision problems. J ACM 25(1):116–133MathSciNetCrossRefMATH

Ibarra OH, Jiang T, Tran NQ, Wang H (1995) New decidability results concerning two-way counter machines. SIAM J Comput 24(1):123–137MathSciNetCrossRefMATH

Jonoska N, Mahalingam K, Chen J (2005) Involution codes: with application to DNA coded languages. Nat Comput 4(2):141–162MathSciNetCrossRef

Jonoska N, Kari L, Mahalingam K (2008) Involution solid and join codes. Fundamenta Informaticae 86(1,2):127–142MathSciNetMATH

Kari L, Mahalingham K (2006) DNA codes and their properties. In: Proceedings of the 12th international meeting on DNA computing, pp 127–142

Kari L, Lossevsa E, Konstantinidis S, Sosik P, Thierrin G (2006) A formal language analysis of DNA hairpin structures. Fundamenta Informaticae 71(4):453–475MathSciNetMATH

Minsky M (1961) Recursive unsolvability of Post’s problem of Tag and other topics in the theory of Turing machines. Ann Math 74:437–455MathSciNetCrossRefMATH

Title: On decidability and closure properties of language classes with respect to bio-operations
Author: Oscar H. Ibarra
Publication date: 01-06-2016
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 2/2016
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-015-9500-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2016

Probability 1 computation with chemical reaction networks

Classical, quantum and biological randomness as relative unpredictability

Emulating cellular automata in chemical reaction–diffusion networks

Global memory schemes for dynamic optimization

Development of firefly algorithm via chaotic sequence and population diversity to enhance the image contrast

Physarum in silicon: the Greek motorways study

Premium Partner