Some results on top-context-free tree languages

Dieter Hofbauer, Maria Huber, Gregory Kucherov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

Top-context-free tree languages (called corégulier by Arnold and Dauchet [1, 2]) constitute a natural subclass of context-free tree languages. In this paper, we give further evidence for the importance of this class by exhibiting certain closure properties. We systematically treat closure under the operations replacement and substitution as well as under the corresponding iteration operations. Several other well-known language classes are considered as well. Furthermore, various characterizations of the regular top-context-free languages are given, among others by means of restricted regular expressions.

Original languageEnglish
Title of host publicationTrees in Algebra and Programming - 19th International Colloquium CAAP 1994, Proceedings
EditorsSophie Tison
PublisherSpringer Verlag
Pages157-171
Number of pages15
ISBN (Print)9783540578796
Publication statusPublished - 1994
Externally publishedYes
Event19th Colloquium on Trees in Algebra and Programming, CAAP 1994 - Edinburgh, United Kingdom
Duration: 11 Apr 199413 Apr 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume787 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th Colloquium on Trees in Algebra and Programming, CAAP 1994
Country/TerritoryUnited Kingdom
CityEdinburgh
Period11/04/9413/04/94

Fingerprint

Dive into the research topics of 'Some results on top-context-free tree languages'. Together they form a unique fingerprint.

Cite this