One-pass reductions
We study OI and IO one-pass reduction sequences with term rewrite systems. We present second order decidability and undecidability results on recognizable tree languages and one-pass reductions. For left-linear TRSs, the second order OI inclusion problem and the second order OI reachability problem...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2016
|
| Sorozat: | Acta cybernetica
22 No. 3 |
| Kulcsszavak: | Programozás |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.22.3.2016.6 |
| Online Access: | http://acta.bibl.u-szeged.hu/40267 |
| Tartalmi kivonat: | We study OI and IO one-pass reduction sequences with term rewrite systems. We present second order decidability and undecidability results on recognizable tree languages and one-pass reductions. For left-linear TRSs, the second order OI inclusion problem and the second order OI reachability problem are decidable, the second order OI joinability problem is undecidable. For right-linear TRSs, the second order common IO ancestor problem is undecidable. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 633-655 |
| ISSN: | 0324-721X |