On the isomorphism problem for decision trees and decision lists

DOI10.1016/J.TCS.2015.01.025MaRDI QIDQ2348033zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan, Yadu Vasudev

Publication date 10 June 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.01.025

zbMATH Keywords

Boolean function isomorphismgraph isomorphismlogspace completeness

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the isomorphism problem for decision trees and decision lists
• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• Isomorphism testing of Boolean functions computable by constant-depth circuits
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Testing Boolean function isomorphism

Cites work

• Completeness results for graph isomorphism.
• Complexity measures and decision tree complexity: a survey.
• Constant depth circuits, Fourier transform, and learnability
• Counting quantifiers, successor relations, and logarithmic space
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• Hypergraph isomorphism and structural equivalence of Boolean functions
• Learning decision trees from random examples
• Learning Decision Trees Using the Fourier Spectrum
• On the isomorphism of expressions
• On truth-table reducibility to SAT
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• STACS 2004
• The complexity of satisfiability problems
• The computational complexity of equivalence and isomorphism problems
• The Formula Isomorphism Problem
• The isomorphism problem for \(k\)-trees is complete for logspace
• Undirected connectivity in log-space
• Which problems have strongly exponential complexity?

Cited in

(2)

• On the isomorphism problem for decision trees and decision lists
• A syntactic characterization of bounded-rank decision trees in terms of decision lists

This page was built for publication: On the isomorphism problem for decision trees and decision lists

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