scientific article; zbMATH DE number 1223619

zbMath0911.03006MaRDI QIDQ4218930

Hubert Comon, Yan Jurski

Publication date: 15 November 1998

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

decidabilityNP-completetree automatalambda calculushigher-order unificationhigher-order matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Combinatory logic and lambda calculus (03B40)

Related Items

Reachability in Succinct and Parametric One-Counter Automata ⋮ Tractable and intractable second-order matching problems ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Decidability of bounded higher-order unification ⋮ Reachability in Parameterized Systems: All Flavors of Threshold Automata ⋮ On the expressive power of schemes ⋮ Higher-order matching for program transformation ⋮ Dependency Tree Automata ⋮ Recognizability in the Simply Typed Lambda-Calculus ⋮ On the undecidability of second-order unification ⋮ Model-Checking Games for Typed λ-Calculi