Conference paper

Decidability of operation problems for TOL languages and subclasses


Authors listBordihn, Henning; Holzer, Markus; Kutrib, Martin

Publication year2011

Pages344-352

JournalInformation and Computation

Volume number209

Issue number3

ISSN0890-5401

DOI Linkhttps://doi.org/10.1016/j.ic.2010.11.008

Conference3rd International Conference on Language and Automata Theory and Applications

PublisherElsevier


Abstract
We investigate the decidability of the operation problem for TOL languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (OL languages, TOL languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of OL and TOL languages and their propagating variants are not even semidecidable. The situation changes for unary OL languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable. (C) 2010 Elsevier Inc. All rights reserved.



Citation Styles

Harvard Citation styleBordihn, H., Holzer, M. and Kutrib, M. (2011) Decidability of operation problems for TOL languages and subclasses, Information and computation, 209(3), pp. 344-352. https://doi.org/10.1016/j.ic.2010.11.008

APA Citation styleBordihn, H., Holzer, M., & Kutrib, M. (2011). Decidability of operation problems for TOL languages and subclasses. Information and computation. 209(3), 344-352. https://doi.org/10.1016/j.ic.2010.11.008



Keywords


CELLULAR INTERACTIONSDecidabilityFILAMENTSINPUTSL systemsMATHEMATICAL MODELSOperation problemUnary languages

Last updated on 2025-02-04 at 02:56