A view of computability on term algebras

DOI10.1016/0022-0000(83)90008-9zbMath0514.68053OpenAlexW2019794090MaRDI QIDQ1051428

Frank M. Hawrusik, K. N. Venkataraman, Ann Yasuhara

Publication date: 1983

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(83)90008-9

zbMATH Keywords

decidabilitylogiccomputational theorypartial recursive functionsLISPfinite binary treespebble games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Necessary and sufficient conditions for the universality of programming formalisms

Cites Work

• Straight-line program length as a parameter for complexity analysis
• The algebraic specification of abstract data types
• Linear unification
• On formalised computer programs
• Proof of correctness of data representations
• Undecidable theories
• Fast Decision Procedures Based on Congruence Closure
• Relative complexity of algebras
• Reasoning About Recursively Defined Data Structures
• Recursive data structures
• Proving Properties of Complex Data Structures
• Abstract data types and the development of data structures
• On Time Versus Space
• Initial Algebra Semantics and Continuous Algebras
• Space bounds for a game on graphs
• The Diophantine Problem for Addition and Divisibility
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Data type specification
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Definability and decision problems in arithmetic
• On relations as coextensive with classes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A view of computability on term algebras