Linear generalized semi-monadic rewrite systems effectively preserve recognizability

DOI10.1016/S0304-3975(96)00333-7zbMath0902.68092MaRDI QIDQ1127543

Pál Gyenizse, Sándor Vágvölgyi

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (15)

Right-linear half-monadic term rewrite systems ⋮ 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 ⋮ Decidability for left-linear growing term rewriting systems. ⋮ Term rewriting restricted to ground terms. ⋮ Tree automata for rewrite strategies ⋮ Normalization properties for shallow TRS and innermost rewriting ⋮ Murg term rewrite systems ⋮ Reachability analysis over term rewriting systems ⋮ Termination criteria for tree automata completion ⋮ TAGED Approximations for Temporal Properties Model-Checking ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Congruential complements of ground term rewrite systems ⋮ A property of left-linear rewrite systems preserving recognizability

Cites Work

• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Reductions in tree replacement systems
• Deterministic tree pushdown automata and monadic tree rewriting systems
• On injectivity of deterministic top-down tree transducers
• Bottom-up tree pushdown automata: Classification and connection with rewrite systems
• Decidability of reachability for disjoint union of term rewriting systems
• Undecidable properties of deterministic top-down tree transducers
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Tree generating regular systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Linear generalized semi-monadic rewrite systems effectively preserve recognizability