Reductions in tree replacement systems
From MaRDI portal
Publication:1082092
DOI10.1016/0304-3975(85)90089-1zbMath0602.68072OpenAlexW1979568806MaRDI QIDQ1082092
Jean H. Gallier, Ronald V. Book
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90089-1
word problemconfluent systemcongruence classesreduction systemsChurch- Rosser tree replacement systemsirreducible treeNoetherian systemnormed rewriting systemtree pushdown automatontree reducing machine
Related Items
Bottom-up tree pushdown automata: Classification and connection with rewrite systems, Decidability of reachability for disjoint union of term rewriting systems, Computing linearizations using test sets, Ground reducibility is EXPTIME-complete, 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, Attacking a public key cryptosystem based on tree replacement, Deterministic tree pushdown automata and monadic tree rewriting systems, Linear generalized semi-monadic rewrite systems effectively preserve recognizability, Term rewriting restricted to ground terms., On ground-confluence of term rewriting systems, Tree automata for rewrite strategies, Specification and proof in membership equational logic, Decidability of regularity and related properties of ground normal form languages, Some undecidability results concerning the property of preserving regularity, CHAP and rewrite components, Congruential complements of ground term rewrite systems, A property of left-linear rewrite systems preserving recognizability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Orderings for term-rewriting systems
- Computing in systems described by equations
- New decision algorithms for finitely presented commutative semigroups
- Testing for the Church-Rosser property
- Monadic Thue systems
- Tree acceptors and some of their applications
- On theories with a combinatorial definition of 'equivalence'
- Pushdown tree automata
- On Uniquely Decipherable Codes with Two Codewords
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- Complete Sets of Reductions for Some Equational Theories
- Programming with Equations
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Tree generating regular systems
- Tree-Manipulating Systems and Church-Rosser Theorems
- The word problem
