Graph-controlled insertion-deletion systems generating language classes beyond linearity

DOI10.1007/978-3-319-60252-3_10zbMath1410.68186OpenAlexW2621321853MaRDI QIDQ2400996

Indhumathi Raman, Lakshmanan Kuppusamy, Henning Fernau

Publication date: 31 August 2017

Full work available at URL: https://hal.inria.fr/hal-01657011/file/440206_1_En_10_Chapter.pdf

zbMATH Keywords

insertion-deletion systemsdescriptional complexity measuresgraph-controlled systemsclosure classes of linear languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (7)

Parsimonious computational completeness ⋮ On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2 ⋮ Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1) ⋮ On path-controlled insertion-deletion systems

This page was built for publication: Graph-controlled insertion-deletion systems generating language classes beyond linearity