The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
From MaRDI portal
Publication:3636833
DOI10.1007/978-3-642-02348-4_24zbMath1242.68141OpenAlexW1505655634MaRDI QIDQ3636833
Publication date: 30 June 2009
Published in: Rewriting Techniques and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02348-4_24
Related Items
Levels of undecidability in rewriting, Behavioral Rewrite Systems and Behavioral Productivity, Complexity of Fractran and Productivity, Well-Definedness of Streams by Termination, Degrees of Undecidability in Term Rewriting
Cites Work
- Unnamed Item
- Unnamed Item
- Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
- The Church-Rosser property for ground term-rewriting systems is decidable
- A term calculus for (co-)recursive definitions on streamlike data structures
- Term Rewriting and All That
- Productivity of Stream Definitions
- Equality of streams is a Π0 over 2-complete problem
- Data-Oblivious Stream Productivity
- Strong Computability and Variants of the Uniform Halting Problem