[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Investigations on the power of matrix insertion-deletion systems with small sizes

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

Matrix insertion-deletion systems combine the idea of matrix control (a control mechanism well established in regulated rewriting) with that of insertion and deletion (as opposed to replacements). Given a matrix insertion-deletion system, the size of such a system is given by a septuple of integers \((k;n,i',i'';m,j',j'')\). The first integer k denotes the maximum number of rules in (length of) any matrix. The next three parameters \(n,i',i''\) denote the maximal length of the insertion string, the maximal length of the left context, and the maximal length of the right context of insertion rules, respectively. The last three parameters \(m,j',j''\) are similarly understood for deletion rules. In this paper, we improve on and complement previous computational completeness results for such systems, showing that matrix insertion-deletion systems of size (1) (3; 1, 0, 1; 1, 0, 1), (3; 1, 0, 1; 1, 1, 0), (3; 1, 1, 1; 1, 0, 0) and (3; 1, 0, 0; 1, 1, 1) (2) (2; 1, 0, 1; 2, 0, 0), (2; 2, 0, 0; 1, 0, 1), (2; 1, 1, 1; 1, 1, 0) and (2; 1, 1, 0; 1, 1, 1), are computationally complete. Further, we also discuss linear and metalinear languages and we show how to simulate grammars characterizing them by matrix insertion-deletion systems of size (3; 1, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), (2; 2, 1, 0; 1, 0, 0) and (2; 2, 0, 1; 1, 0, 0). We also generate non-semilinear languages using matrices of length three with context-free insertion and deletion rules.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Alhazov A, Krassovitskiy A, Rogozhin Y, Verlan S (2011) P systems with minimal insertion and deletion. Theoret Comput Sci 412(1–2):136–144

    Article  MathSciNet  MATH  Google Scholar 

  • Benne R (ed) (1993) RNA editing: the alteration of protein coding sequences of RNA. Series in molecular biology. Ellis Horwood, Chichester

    Google Scholar 

  • Biegler F, Burrell MJ, Daley M (2007) Regulated RNA rewriting: modelling RNA editing with guided insertion. Theor Comput Sci 387(2):103–112

    Article  MathSciNet  MATH  Google Scholar 

  • Dassow J, Păun Gh (1985) Further remarks on the complexity of regulated rewriting. Kybernetica 21(3):213–227

    MathSciNet  MATH  Google Scholar 

  • Dassow J, Păun G (1989) Regulated rewriting in formal language theory, volume 18 of EATCS monographs in theoretical computer science. Springer, Berlin

    Book  Google Scholar 

  • Fernau H (2003) Nonterminal complexity of programmed grammars. Theor Comput Sci 296:225–251

    Article  MathSciNet  MATH  Google Scholar 

  • Fernau H, Kuppusamy L (2017) Parikh images of matrix ins-del systems. In: Gopal TV, Jäger G, Steila S (eds) Theory and applications of models of computation, TAMC (LNCS), vol 10185. Springer, pp 201–215

  • Freund R, Păun G (2001) On the number of non-terminal symbols in graph-controlled, programmed and matrix grammars. In: Margenstern M, Rogozhin Y (eds) Machines, computations, and universality; 3rd MCU (LNCS), vol 2055, pp 214–225

  • Fernau H, Freund R, Oswald M, Reinhardt K (2007) Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars. J Autom Lang Comb 12(1/2):117–138

    MathSciNet  MATH  Google Scholar 

  • Freund R, Kogler M, Rogozhin Y, Verlan S (2010) Graph-controlled insertion-deletion systems. In: McQuillan I, Pighizzini G (eds) Proceedings twelfth annual workshop on descriptional complexity of formal systems, DCFS (EPTCS), vol 31, pp 88–98

  • Fernau H, Kuppusamy L, Raman I (2016) Generative power of matrix insertion-deletion systems with context-free insertion or deletion. In: Amos M, Condon A (eds) Unconventional computation and natural computation conference, UCNC (LNCS), vol 9726. Springer, pp 35–48

  • Fernau H, Kuppusamy L, Raman I (2017a) Graph-controlled insertion-deletion systems generating language classes beyond linearity. In: Pighizzini G, Câmpeanu C (eds) Descriptional complexity of formal systems: 19th IFIP WG 1.02 international conference, DCFS (LNCS), vol 10316. Springer, pp 128–139

  • Fernau H, Kuppusamy L, Raman I (2017b) On the generative power of graph-controlled insertion-deletion systems with small sizes. J Autom Lang Comb 22:61–92

    MathSciNet  MATH  Google Scholar 

  • Fernau H, Kuppusamy L, Raman I (2017c) Properties of language classes between linear and context-free. Manuscript in preparation

  • Galiukschov BS (1981) Semicontextual grammars (in Russian). Mat. logica i mat. ling., Kalinin Univ., pp 38–50

  • Geffert V (1991a) How to generate languages using only two pairs of parentheses. J Inf Process Cybern EIK 27(5/6):303–315

    MATH  Google Scholar 

  • Geffert V (1991b) Normal forms for phrase-structure grammars. RAIRO Inf théor Appl/Theor Inf Appl 25:473–498

    Article  MathSciNet  MATH  Google Scholar 

  • Herman GT (1968) The halting problem of one state Turing machines with \(n\)-dimensional tape. Z Math Log Grundl Math 14:185–191

    Article  MathSciNet  MATH  Google Scholar 

  • Hopcroft JE, Pansiot J-J (1979) On the reachability problem for 5-dimensional vector addition systems. Theor Comput Sci 8:135–159

    Article  MathSciNet  MATH  Google Scholar 

  • Ivanov S, Verlan S (2015) Random context and semi-conditional insertion-deletion systems. Fundam Inform 138:127–144

    MathSciNet  MATH  Google Scholar 

  • Ivanov S, Verlan S (2017) Universality and computational completeness of controlled leftist insertion-deletion systems. Fundam Inform 155(1–2):163–185

    Article  MathSciNet  MATH  Google Scholar 

  • Kallmeyer L (2010) On mildly context-sensitive non-linear rewriting. Res Lang Comput 8:341–363

    Article  MathSciNet  Google Scholar 

  • Kari L (1991) On insertion and deletion in formal languages. PhD thesis, University of Turku, Finland

  • Kari L, Thierrin G (1996) Contextual insertions/deletions and computability. Inf Comput 131(1):47–61

    Article  MathSciNet  MATH  Google Scholar 

  • Krassovitskiy A, Rogozhin Y, Verlan S (2008) Further results on insertion-deletion systems with one-sided contexts. In: Martín-Vide C, Otto F, Fernau H (eds) Language and automata theory and applications, second international conference, LATA (LNCS), vol 5196. Springer, pp 333–344

  • Kudlek M (1996) Small deterministic Turing machines. Theor Comput Sci 168(2):241–255

    Article  MathSciNet  MATH  Google Scholar 

  • Kuppusamy L, Rama R (2003) On the power of tissue P systems with insertion and deletion rules. In: Pre-proc of workshop on membrane computing, volume 28 of Report RGML. Univ. Tarragona, Spain, pp 304–318

  • Kuppusamy L, Mahendran A (2016) Modelling DNA and RNA secondary structures using matrix insertion-deletion systems. Int J Appl Math Comput Sci 26(1):245–258

    Article  MathSciNet  MATH  Google Scholar 

  • Kuppusamy L, Mahendran A, Krishna SN (2011) Matrix insertion-deletion systems for bio-molecular structures. In: Natarajan R, Ojo AK (eds) Distributed computing and internet technology—7th international conference, ICDCIT (LNCS), vol 6536. Springer, pp 301–312

  • Kuppusamy L, Raman I, Krithivasan K (2016) On succinct description of certain context-free languages by ins-del and matrix ins-del systems. Int J Found Comput Sci 27(7):775–786

    Article  MathSciNet  MATH  Google Scholar 

  • Kuroda S-Y (1964) Classes of languages and linear-bounded automata. Inf Control (now Inf Comput) 7:207–223

    Article  MathSciNet  MATH  Google Scholar 

  • Kutrib M, Malcher A (2007) Finite turns and the regular closure of linear context-free languages. Discret Appl Math 155(16):2152–2164

    Article  MathSciNet  MATH  Google Scholar 

  • Marcus S (1969) Contextual grammars. Rev Roum Math Pures et Appl 14:1525–1534

    MathSciNet  MATH  Google Scholar 

  • Marcus M, Păun Gh (1990) Regulated Galiukschov semicontextual grammars. Kybernetika 26(4):316–326

    MathSciNet  MATH  Google Scholar 

  • Margenstern M, Păun Gh, Rogozhin Y, Verlan S (2005) Context-free insertion-deletion systems. Theor Comput Sci 330(2):339–348

    Article  MathSciNet  MATH  Google Scholar 

  • Michaelis J, Kracht M (1997) Semilinearity as a syntactic invariant. In: Retoré C (ed) Logical aspects of computational linguistics, first international conference, LACL’96 (LNCS), vol 1328. Springer, pp 329–345

  • Neary T (2017) 2-state 2-symbol Turing machines with periodic support produce regular sets. In: Pighizzini G, Câmpeanu C (eds) Descriptional complexity of formal systems—19th IFIP WG 1.02 international conference, DCFS (LNCS), vol 10316. Springer, pp 274–286

  • Neary T, Woods D (2012) The complexity of small universal Turing machines: A survey. In: Bieliková M, Friedrich G, Gottlob G, Katzenbeisser S, Turán Gy (eds) SOFSEM 2012: theory and practice of computer science—38th conference on current trends in theory and practice of computer science (LNCS), vol 7147. Springer, pp 385–405

  • Otto F (2006) Restarting automata. In: Ésik Z, Martín-Vide C, Mitrana V (eds) Recent advances in formal languages and applications. Studies in computational intelligence, vol 25. Springer, pp 269–303

  • Parikh RJ (1966) On context-free languages. J ACM 13(4):570–581

    Article  MATH  Google Scholar 

  • Păun Gh (1984) Six nonterminals are enough for generating each r.e. language by a matrix grammar. Int J Comput Math 15(1–4):23–37

    MathSciNet  MATH  Google Scholar 

  • Păun Gh, Rozenberg G, Salomaa A (1998) DNA computing: new computing paradigms. Springer, Berlin

    Book  MATH  Google Scholar 

  • Penttonen M (1974) One-sided and two-sided context in formal grammars. Inf Control (now Inf Comput) 25:371–392

    Article  MathSciNet  MATH  Google Scholar 

  • Petre I, Verlan S (2012) Matrix insertion-deletion systems. Theor Comput Sci 456:80–88

    Article  MathSciNet  MATH  Google Scholar 

  • Salomaa AK (1973) Formal languages. Academic Press, Cambridge

    MATH  Google Scholar 

  • Shannon CE (1956) A universal Turing machine with two internal states. In: Shannon C E, McCarthy J (eds) Automata studies. Annals of mathematics studies, vol 34. Princeton University Press, pp 157–165

  • Stabler E (2004) Varieties of crossing dependencies: structure dependence and mild context sensitivity. Cognit Sci 28:699–720

    Article  Google Scholar 

  • Takahara A, Yokomori T (2003) On the computational power of insertion-deletion systems. Nat Comput 2(4):321–336

    Article  MathSciNet  MATH  Google Scholar 

  • Verlan S (2007) On minimal context-free insertion-deletion systems. J Autom Lang Comb 12(1–2):317–328

    MathSciNet  MATH  Google Scholar 

  • Verlan S (2010) Recent developments on insertion-deletion systems. Comput Sci J Mold 18(2):210–245

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are grateful to Serghei Verlan for his comments on our previous UCNC version, and also for sharing with us his Perl tool (simulating graph-controlled ins-del systems) that facilitates checking some of our results and examples. Some extension part of the work was undertaken during the second author’s visit to University of Trier, Germany, in June 2016. Support of this visit by overhead money (from DFG grant FE 560/6-1) is gratefully acknowledged.

Author information

Authors and Affiliations

  1. Fachbereich 4 - Abteilung Informatikwissenschaften, CIRT, Universität Trier, 54286, Trier, Germany

    Henning Fernau

  2. School of Computer Science and Engineering, VIT University, Vellore, 632 014, India

    Lakshmanan Kuppusamy

  3. School of Information Technology and Engineering, VIT University, Vellore, 632 014, India

    Indhumathi Raman

Authors
  1. Henning Fernau
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lakshmanan Kuppusamy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Indhumathi Raman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Henning Fernau.

Additional information

A preliminary version of this paper appeared in Proceedings of UCNC 2016, LNCS 9726, pp. 35–48, 2016.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fernau, H., Kuppusamy, L. & Raman, I. Investigations on the power of matrix insertion-deletion systems with small sizes. Nat Comput 17, 249–269 (2018). https://doi.org/10.1007/s11047-017-9656-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-017-9656-8

Keywords

Search

Navigation