An axiomatic approach to the Korenjak-Hopcroft algorithms

DOI10.1007/BF01744577zbMath0581.68032MaRDI QIDQ3703289

No author found.

Publication date: 1983

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

grammarstransducersprogram schemesaxiomatic approach to algorithmsdeterministic top-down tree transductions of infinite treesequivalence decision algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65) Algorithms in computer science (68W99)

Related Items (13)

A fast algorithm to decide on the equivalence of stateless DPDA ⋮ The extended equivalence problem for a class of non-real-time deterministic pushdown automata ⋮ Prime normal form and equivalence of simple grammars ⋮ Graphes canoniques de graphes algébriques ⋮ The equivalence problem for deterministic pushdown automata is decidable ⋮ A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict ⋮ Equivalence of simple functions ⋮ Unnamed Item ⋮ Complete formal systems for equivalence problems ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata ⋮ The monadic second-order logic of graphs. IV: Definability properties of equational graphs ⋮ \(L(A)=L(B)\)? A simplified decidability proof.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamental properties of infinite trees
• A system which automatically improves programs
• Completeness results for the equivalence of recursive schemas
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• A direct algorithm for checking equivalence of LL(k) grammars
• A representation of trees by languages. I
• Proving and applying program transformations expressed with second-order patterns
• On equivalence of grammars through transformation trees
• Strict deterministic grammars
• On the equivalence problem for attribute systems
• Infinite trees in normal form and recursive equations having a unique solution
• The equivalence problem for real-time strict deterministic languages
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Equivalence problems for mappings on infinite strings
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• Tree-Manipulating Systems and Church-Rosser Theorems

This page was built for publication: An axiomatic approach to the Korenjak-Hopcroft algorithms