Decidability of the existential theory of infinite terms with subterm relation

DOI10.1006/INCO.1994.1001zbMath0801.68115OpenAlexW1995502356MaRDI QIDQ1314267

Sauro Tulipani

Publication date: 22 February 1994

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1994.1001

zbMATH Keywords

decidabilityrational treesinfinite treesinductively defined data structuressubterm relationterm algebras

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25) Data structures (68P05)

Related Items (3)

\(\Sigma_ 1^ 1\)-completeness of a fragment of the theory of trees with subtree relation ⋮ Complete axiomatizations of some quotient term algebras ⋮ On equality up-to constraints over finite trees, context unification, and one-step rewriting

This page was built for publication: Decidability of the existential theory of infinite terms with subterm relation