Ground reducibility is EXPTIME-complete

From MaRDI portal
Revision as of 13:07, 1 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:1887142

DOI10.1016/S0890-5401(03)00134-2zbMath1090.68047OpenAlexW2133563196MaRDI QIDQ1887142

Florent Jacquemard, Hubert Comon

Publication date: 23 November 2004

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

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00134-2

zbMATH Keywords

Computational complexityTree automataRewriting systemsComputer theorem-proving


Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)


Related Items

A proof method for local sufficient completeness of term rewriting systems, Alternating two-way AC-tree automata, Test sets for the universal and existential closure of regular tree languages., Sufficient completeness verification for conditional and constrained TRS, Automated Induction with Constrained Tree Automata, Specification and proof in membership equational logic, Reducibility of operation symbols in term rewriting systems and its application to behavioral specifications, Proving weak properties of rewriting, The HOM Problem is EXPTIME-Complete, Unique Normalization for Shallow TRS, Induction = I-axiomatization + first-order consistency., Non-linear rewrite closure and weak normalization, Emptiness and finiteness for tree automata with global reflexive disequality constraints



Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1887142&oldid=14290388"
Powered by MediaWiki