Rigid reachability

DOI10.1007/3-540-49366-2_2MaRDI QIDQ4249176zbMATH OpenFDO

Authors Harald Ganzinger, Florent Jacquemard, Margus Veanes

Publication date 12 January 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49366-2_2

zbMATH Keywords

automata-theoretic methodsdecidable subclassesEXPTIME-completerigid \(E\)-unificationrigid reachabilitysecond-order unificationundecidability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION
• Decidable fragments of simultaneous rigid reachability
• Monadic simultaneous rigid E-unification
• Monadic simultaneous rigid E-unification and related problems
• Special cases and substitutes for rigid \(E\)-unification

Cited in

(7)

• Reachability and confluence are undecidable for flat term rewriting systems
• Farmer's theorem revisited
• Logic with equality: Partisan corroboration and shifted pairing
• On the undecidability of second-order unification
• Tractable and intractable second-order matching problems
• Decidable fragments of simultaneous rigid reachability
• One is all you need: associative second-order unification without first-order variables

This page was built for publication: Rigid reachability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249176)