Sufficient-completeness, ground-reducibility and their complexity
From MaRDI portal
Publication:2641108
DOI10.1007/BF01893885zbMath0721.68032MaRDI QIDQ2641108
Paliath Narendran, Daniel J. Rosenkrantz, Deepak Kapur, Han-Tao Zhang
Publication date: 1991
Published in: Acta Informatica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)
Related Items
Ground reducibility is EXPTIME-complete, On relationship between term rewriting systems and regular tree languages, New uses of linear arithmetic in automated theorem proving by induction, On First-Order Model-Based Reasoning, Test sets for the universal and existential closure of regular tree languages., Sufficient completeness verification for conditional and constrained TRS, Stability of termination and sufficient-completeness under pushouts via amalgamation, Undecidability of ground reducibility for word rewriting systems with variables, Incremental Proofs of Termination, Confluence and Sufficient Completeness of OBJ Specifications, Behavioral Rewrite Systems and Behavioral Productivity, Narrowing based procedures for equational disunification, Inst-Gen – A Modular Approach to Instantiation-Based Automated Reasoning, Lazy productivity via termination, On deciding subsumption problems, Automating inductionless induction using test sets, Explicit versus implicit representations of subsets of the Herbrand universe., Induction = I-axiomatization + first-order consistency., Working with ARMs: Complexity results on atomic representations of Herbrand models
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Proofs by induction in equational theories with constructors
- The complexity of monadic recursion schemes: Exponential time bounds
- Complete problems in the first-order predicate calculus
- On sufficient-completeness and related properties of term rewriting systems
- Proof by consistency
- Explicit representation of terms defined by counter examples
- Complexity results for classes of quantificational formulas
- Computing with rewrite systems
- Semantic confluence tests and completion methods
- Abstract Data Type Specification in the Affirm System
- Confluent and Other Types of Thue Systems
- Complete Sets of Reductions for Some Equational Theories
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
