2013/10/03 by Tatsuya Akutsu, Akutsu, Tatsuya, Takeyuki Tamura +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #FOS: Computer and information sciences #Symbolic Computation (cs.SC) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1310.0919
openalex publication_date 2013/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the unification problem with associative, commutative, and associative-commutative functions mainly from a viewpoint of the parameterized complexity on the number of variables. It is shown that both associative and associative-commutative unification problems are W[1]-hard. A fixed-parameter algorithm and a polynomial-time algorithm are presented for special cases of commutative unification in which one input term is variable-free and the number of variables is bounded by a constant, respectively. Related results including those on the string and tree edit distance problems with variables are shown too.