Haskell overloading is DEXPTIME-complete

DOI10.1016/0020-0190(94)00130-8MaRDI QIDQ1336737zbMATH OpenOpenAlexWikidataFDO

Authors Helmut Seidl

Publication date 16 April 1996

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)00130-8

zbMATH Keywords

complexity analysisDEXPTIMEHaskell type system

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 125891
• scientific article; zbMATH DE number 1301739
• An analysis of ML typability
• Lower bounds on type checking overloading
• An analysis of the Core-ML language: Expressive power and type reconstruction

Cites work

• Deciding equivalence of finite tree automata
• scientific article; zbMATH DE number 125891 (Why is no real title available?)

Cited in

(31)

• Efficient inclusion checking for deterministic tree automata and XML schemas
• Deciding H₁ by resolution
• Lower bounds on type checking overloading
• Decidability and complexity of simultaneous rigid E-unification with one variable and related results
• Balancedness of MSO transductions in polynomial time
• Tree automata with one memory set constraints and cryptographic protocols
• Unification modulo ACUI plus distributivity axioms
• The complexity of the exponential output size problem for top-down and bottom-up tree transducers
• Ground reducibility is EXPTIME-complete
• Alternating two-way AC-tree automata
• Tree automata with equality constraints modulo equational theories
• Transducer-based analysis of cryptographic protocols
• Abstraction and resolution modulo AC: How to verify Diffie--Hellman-like protocols automatically
• Set constraints with intersection
• A survey on decidable equivalence problems for tree transducers
• Parameterized Verification of Communicating Automata under Context Bounds
• Rigid Tree Automata
• scientific article; zbMATH DE number 125891 (Why is no real title available?)
• An analysis of ML typability
• An analysis of the Core-ML language: Expressive power and type reconstruction
• RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION
• Queries on XML streams with bounded delay and concurrency
• Rigid tree automata and applications
• On the complexity of typechecking top-down XML transformations
• Unification of concept terms in description logics
• A proof procedure for separation logic with inductive definitions and data
• Ramsey quantifiers over automatic structures: complexity and applications to verification
• Probabilistic temporal reasoning using superposition semantics
• Restricted unification in the DL \(\mathcal{FL}_0\)
• Tree tuple languages from the logic programming point of view
• Typechecking top-down XML transformations: Fixed input or output schemas

Describes a project that uses

Uses Software

• Haskell

This page was built for publication: Haskell overloading is DEXPTIME-complete

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