The Boolean closure of DR-recognizable tree languages
The family DRec of tree languages recognized by deterministic root-tofrontier (top-down) tree automata is not closed under unions or complements. Hence, it is not a variety of tree languages in the sense of Steinby. However, we show that the Boolean closure of DRec is a variety which is properly inc...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
1992
|
| Sorozat: | Acta cybernetica
10 No. 4 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12511 |
| Tartalmi kivonat: | The family DRec of tree languages recognized by deterministic root-tofrontier (top-down) tree automata is not closed under unions or complements. Hence, it is not a variety of tree languages in the sense of Steinby. However, we show that the Boolean closure of DRec is a variety which is properly included in the variety Rec of all recognizable tree languages. This Boolean closure is also compared with some other tree language varieties. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 255-272 |
| ISSN: | 0324-721X |