One-Pass Reductions

Vágvölgyi, Sándor: One-Pass Reductions. Acta cybernetica, (22) 3. pp. 633-655. (2016)

[img] Cikk, tanulmány, mű
actacyb_22_3_2016_6.pdf

Download (369kB)

Abstract

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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2016
Volume: 22
Number: 3
Page Range: pp. 633-655
ISSN: 0324-721X
DOI: https://doi.org/10.14232/actacyb.22.3.2016.6
Uncontrolled Keywords: Programozás - kifejezés újraírása
Date Deposited: 2017. Mar. 16. 13:37
Last Modified: 2018. Jun. 06. 19:02
URI: http://acta.bibl.u-szeged.hu/id/eprint/40267

Actions (login required)

View Item View Item