Linear generalized semi-monadic rewrite systems effectively preserve recognizability

DOI10.1016/S0304-3975(96)00333-7MaRDI QIDQ1127543zbMATH OpenFDO

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

Publication date 13 August 1998

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

Full work available at URL https://doi.org/10.1016/S0304-3975(96)00333-7

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• A property of left-linear rewrite systems preserving recognizability
• Rewriting preserving recognizability of finite tree languages
• scientific article; zbMATH DE number 5708984
• scientific article; zbMATH DE number 176501
• scientific article; zbMATH DE number 794243

Cites work

• Bottom-up tree pushdown automata: Classification and connection with rewrite systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Decidability of reachability for disjoint union of term rewriting systems
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Deterministic tree pushdown automata and monadic tree rewriting systems
• scientific article; zbMATH DE number 3872640 (Why is no real title available?)
• scientific article; zbMATH DE number 4135419 (Why is no real title available?)
• scientific article; zbMATH DE number 176501 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 794243 (Why is no real title available?)
• On injectivity of deterministic top-down tree transducers
• Reductions in tree replacement systems
• Tree generating regular systems
• Undecidable properties of deterministic top-down tree transducers

Cited in

(22)

• Some undecidability results concerning the property of preserving regularity
• Bottom-up tree pushdown automata: Classification and connection with rewrite systems
• 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
• Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy
• Right-linear half-monadic term rewrite systems
• Rewriting preserving recognizability of finite tree languages
• Losing recognizability
• Tree automata for rewrite strategies
• scientific article; zbMATH DE number 1615242 (Why is no real title available?)
• scientific article; zbMATH DE number 5708984 (Why is no real title available?)
• TAGED Approximations for Temporal Properties Model-Checking
• scientific article; zbMATH DE number 1508936 (Why is no real title available?)
• scientific article; zbMATH DE number 794243 (Why is no real title available?)
• Bottom-Up Rewriting Is Inverse Recognizability Preserving
• Reachability analysis over term rewriting systems
• Termination criteria for tree automata completion
• Descendants of a recognizable tree language for sets of linear monadic term rewrite rules
• Normalization properties for shallow TRS and innermost rewriting
• Murg term rewrite systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127543)