Haskell overloading is DEXPTIME-complete

DOI10.1016/0020-0190(94)00130-8zbMATH Open0835.68008OpenAlexW2001621593WikidataQ126322776 ScholiaQ126322776MaRDI QIDQ1336737FDOQ1336737

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

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

Cited in

(29)

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

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)