Some undecidability results concerning the property of preserving regularity
From MaRDI portal
Publication:1274984
DOI10.1016/S0304-3975(98)00055-3zbMath0916.68083MaRDI QIDQ1274984
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (8)
Losing recognizability ⋮ Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy ⋮ Descendants of a recognizable tree language for sets of linear monadic term rewrite rules ⋮ Term rewriting restricted to ground terms. ⋮ Deleting string rewriting systems preserve regularity ⋮ Murg term rewrite systems ⋮ A property of left-linear rewrite systems preserving recognizability ⋮ Regular Gröbner bases
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some decision problems about controlled rewriting systems
- Some undecidability results for non-monadic Church-Rosser Thue systems
- Reductions in tree replacement systems
- A closure property of regular languages
- Deterministic tree pushdown automata and monadic tree rewriting systems
- Linear generalized semi-monadic rewrite systems effectively preserve recognizability
- Monadic Thue systems
- When is an extension of a specification consistent? Decidable and undecidable cases
- The undecidability of the semi-unification problem
- Bottom-up tree pushdown automata: Classification and connection with rewrite systems
- Infinite regular Thue systems
- Simulation of Turing machines by a left-linear rewrite rule
- Tree generating regular systems
- The undecidability of the Turing machine immortality problem
- A Note on Pushdown Store Automata and Regular Systems
This page was built for publication: Some undecidability results concerning the property of preserving regularity
