A general structure of trellis-based reduced-state soft-input/soft-output (RS-SISO) algorithms for communication systems based on concatenated finite state machines (FSMs) with large memory is presented. Based on forward and backward reduced-state (RS) recursions, a particular structure for the RS-SISO algorithm can be obtained by setting suitable parameters in the general formulation. Two novel RS-SISO algorithms are proposed based on a bi-directional state reduction paradigm. To assess the performance of the proposed RS-SISO algorithms, numerical simulations are conducted for isolated long intersymbol interference with additive white Gaussian noise (ISI/AWGN) channels and a serially concatenated system given by interleaved trellis coded modulation (TCM) over an ISI/AWGN channel. Simulation results show that low-complexity RS-SISO algorithms can approach the performance of a full-state SISO algorithm. Moreover, one of the novel RS-SISO algorithms is found to be robust in all the considered cases.