The notions of logic synthesis can be traced back to the early 70’s and work conducted at IBM called Logic synthesis system (LSS). This was a rule based transformation system. These looked for patterns in a design and the rule would perform a transformation on that part of the design in order to improve it. Trimeter had a commercial example of this type of system.
Another early development was MacPitts, developed at MIT. MacPitts took system descriptions as input and produced full custom nMOS layouts as output. It was initially commercialized by MetaLogic, but failed to have any success. MIT also licensed the technology to GTE Labs which became the basis for the SILC silicon compiler.
MacPitts and other similar systems were based on algorithmic transformations. These systems basically had two parts, first a technology independent step that made transformations of higher level concepts into Boolean logic and then a second technology mapping phase where the choices of gates or other library elements was made. Algorithmic systems included MIS, BOLD, Silc, AT&T and several other University efforts.
Synopsys (SOCRATES) had a system (originally developed with GE) that was basically a merge of the two approaches. The front end for transformational and the back end had rule based optimization. Synopsys was the first licensee of the Verilog language from Gateway Design Automation (acquired by Cadence who later made Verilog an open language through Accellera and IEEE standardization processes).
Since that time, Synopsys has dominated the logic synthesis market for ASICs, although other tools from Synplicity (acquired by Synopsys) and Exemplar (acquired by Mentor) had success in the FPGA market
As implementation geometries shrank, delays associated with wires grew while gate delays shrank. This created a problem for logic synthesis because timing assumed that gate delays dominated. Wire delays only became known after place and route, which was much further down in the implementation process. Around 90nm, logic synthesis had to become back-end aware. This was not only for timing issues, but required things such as buffer insertion, cell sizing and power reduction techniques, and many other areas where the layout and the design could not be fully separated. This became known as physical synthesis.