The paper by L.J. Stockmeyer and A.R. Meyer from the Massachusetts Institute of Technology explores the computational complexity of various word problems in automata theory, logic, and arithmetic. The authors demonstrate that several of these problems are inherently computationally expensive, with their complexity characterized by exponential time or space requirements on deterministic or nondeterministic Turing machines. The paper introduces and defines several types of word problems, including regular-like expressions over finite sets of letters, integer expressions over nonnegative integers, and Boolean expressions involving Boolean variables. The authors also introduce two binary relations, log-space reducibility and loglinear reducibility, to classify the complexity of these problems. They provide detailed proofs for some specific cases and outline the methods used to derive the results. The paper concludes with a summary of the main findings and discusses open problems, particularly focusing on the complexity of specific word problems involving operations like union, concatenation, and squaring.The paper by L.J. Stockmeyer and A.R. Meyer from the Massachusetts Institute of Technology explores the computational complexity of various word problems in automata theory, logic, and arithmetic. The authors demonstrate that several of these problems are inherently computationally expensive, with their complexity characterized by exponential time or space requirements on deterministic or nondeterministic Turing machines. The paper introduces and defines several types of word problems, including regular-like expressions over finite sets of letters, integer expressions over nonnegative integers, and Boolean expressions involving Boolean variables. The authors also introduce two binary relations, log-space reducibility and loglinear reducibility, to classify the complexity of these problems. They provide detailed proofs for some specific cases and outline the methods used to derive the results. The paper concludes with a summary of the main findings and discusses open problems, particularly focusing on the complexity of specific word problems involving operations like union, concatenation, and squaring.