The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 73 of 1097
Back to Result List

Decidability of operation problems for TOL languages and subclasses

  • 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 thatWe 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.show moreshow less

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:Henning BordihnORCiD, Markus HolzerGND, Martin Kutrib
DOI:https://doi.org/10.1016/j.ic.2010.11.008
ISSN:0890-5401
Title of parent work (English):Information and computation
Publisher:Elsevier
Place of publishing:San Diego
Publication type:Article
Language:English
Year of first publication:2011
Publication year:2011
Release date:2017/03/26
Tag:Decidability; L systems; Operation problem; Unary languages
Volume:209
Issue:3
Number of pages:9
First page:344
Last Page:352
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
Peer review:Referiert
Institution name at the time of the publication:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.