Interoperability #
Aggregation module for bridges to other libraries, currently CSLib.
Complexitylib.Interop.Cslibconnects the machine model to CSLib's step relations and, throughComplexitylib.Interop.Cslib.Regular, to the regular-language and automata theory that CSLib builds on Mathlib'sLanguage: the finite-state scanner that runs a regular language's automaton places it inDSPACE(0), inL, and inP, each proved separately from that scanner (mem_DSPACE_zero_of_isRegular,mem_L_of_isRegular,mem_P_of_isRegular).Complexitylib.Interop.Cslib.MultiTaperuns our machines on CSLib's multi-tape machines, transferringDTIME,DTISP,P, andFPto CSLib's time and space measures.Complexitylib.Interop.Cslib.FromMultiTaperuns CSLib's machines on ours, soPis exactly CSLib's polynomial time.Complexitylib.Interop.Cslib.Circuittranslates between our fan-in-two circuits and CSLib's De Morgan circuits, transferring CSLib's Shannon and Lupanov bounds and characterizingP/polyin CSLib's circuit model.Complexitylib.Interop.Cslib.CircuitClasseslifts these to theSIZEclasses, andComplexitylib.Interop.Cslib.CircuitDepthmatches circuit depth in both directions.