Reductions in tree replacement systems
Certain kinds of Church-Rosser tree replacement systems called reduction systems are studied. The concept of a tree rewriting system with a norm is introduced and studied. A new tree reducing machine which reduces every input tree to an irreducible tree is defined. As a consequence, when the norm under consideration is the size of the tree (the number of nodes), the word problem for finite Church-Rosser reduction systems is decidable in linear time (in the size of the input tree). Church-Rosser monadic reduction systems generalizing the monadic Thue systems of \textit{R. V. Book} [J. Assoc. Comput. Mach. 29, 171-182 (1982; Zbl 0478.68032)] and \textit{R. V. Book}, \textit{M. Jantzen}, and \textit{C. Wrathall} [Theor. Comput. Sci. 19, 231-251 (1982; Zbl 0488.03020)] are also studied. It is shown that every congruence class and every finite union of congruence classes defined by such a system is accepted by a deterministic bottom-up tree pushdown automaton. This new form of a tree automaton is briefly studied.
- Complete Sets of Reductions for Some Equational Theories
- Computing in systems described by equations
- Confluent and Other Types of Thue Systems
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Generalized finite automata theory with an application to a decision problem of second-order logic
- scientific article; zbMATH DE number 3528212 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3299786 (Why is no real title available?)
- Monadic Thue systems
- New decision algorithms for finitely presented commutative semigroups
- On theories with a combinatorial definition of 'equivalence'
- On Uniquely Decipherable Codes with Two Codewords
- Orderings for term-rewriting systems
- Programming with Equations
- Pushdown tree automata
- Testing for the Church-Rosser property
- The word problem
- Tree acceptors and some of their applications
- Tree generating regular systems
- Tree-Manipulating Systems and Church-Rosser Theorems
- Deterministic tree pushdown automata and monadic tree rewriting systems
- Linear generalized semi-monadic rewrite systems effectively preserve recognizability
- Some undecidability results concerning the property of preserving regularity
- Bottom-up tree pushdown automata: Classification and connection with rewrite systems
- Decidability of reachability for disjoint union of 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
- Sequentiality, monadic second-order logic and tree automata.
- Ground reducibility is EXPTIME-complete
- Automata for reduction properties solving
- Specification and proof in membership equational logic
- Tree automata for rewrite strategies
- One-pass reductions
- A learning algorithm for a subclass of tree rewriting systems
- Learning of Church-Rosser tree rewriting systems
- scientific article; zbMATH DE number 3911709 (Why is no real title available?)
- scientific article; zbMATH DE number 4024775 (Why is no real title available?)
- scientific article; zbMATH DE number 4107710 (Why is no real title available?)
- Inductive proofs by specification transformations
- Decidability of confluence and termination of monadic term rewriting systems
- Bottom-up tree pushdown automata and rewrite systems
- On relationship between term rewriting systems and regular tree languages
- Decidable approximations of term rewriting systems
- scientific article; zbMATH DE number 5036081 (Why is no real title available?)
- Decidability of regularity and related properties of ground normal form languages
- Computing linearizations using test sets
- CHAP and rewrite components
- Attacking a public key cryptosystem based on tree replacement
- On ground-confluence of term rewriting systems
- A complete rewriting system for a monoid of tree transformation classes
This page was built for publication: Reductions in tree replacement systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082092)
