The logic synthesis of ultra-high-speed FSMs is presented. The state assignment is based on a well-known method that uses output vectors. This technique is adjusted to include elements of two-level minimization and takes into account the limited number of terms contained in the programmable-AND/fixed-OR logic cell. The state assignment is based on a special form of the binary decision tree. The second phase of the FSM design is logic optimization. The optimization method is based on tristate buffers, thus making possible a one-logic-level FSM structure. The key point is to search partition variables that control the tristate buffers. This technique can also be applied to combinational circuits or the output block of FSMs only. Algorithms for state assignment and optimization are presented and richly illustrated by examples. The method is dedicated to using specific features of complex programmable logic devices. Experimental results prove its effectiveness (e.g., the implementation of the the 16-bit counter requires 136 logic cells and one-logic-cell level instead of 213 cells and four levels). The optimization method using tristate buffers and a state assignment binary decision tree can be directly applied to FPGA-dedicated logic synthesis.