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...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerző: Vágvölgyi Sándor
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
Leíró adatok
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