AbstractWe 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.
Download data is not yet available.
How to Cite
Vágvölgyi, S. (2016). One-Pass Reductions. Acta Cybernetica, 22(3), 633-655. https://doi.org/10.14232/actacyb.22.3.2016.6