Linear generalized semi-monadic rewrite systems effectively preserve recognizability

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

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

Publication date: 13 August 1998

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

Mathematics Subject Classification ID

68Q42: Grammars and rewriting systems

Related Items

Reachability analysis over term rewriting systems, Some undecidability results concerning the property of preserving regularity, Decidability for left-linear growing term rewriting systems., Term rewriting restricted to ground terms., Congruential complements of ground term rewrite systems, A property of left-linear rewrite systems preserving recognizability, Right-linear half-monadic term rewrite systems, Losing recognizability, Tree automata for rewrite strategies, TAGED Approximations for Temporal Properties Model-Checking

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