Component-Based Design by Solving Language Equations

An important step in the design of a complex system is its decompositioninto a number of interacting components, of which some are given (known)and some need to be synthesized (unknown).Then a basic task in the design flow is to synthesize an unknown componentthat when combined with the known part of the system (the context)satisfies a given specification.This problem arises in several applications ranging from sequentialsynthesis to the design of discrete controllers.There are different formulations of the problem, depending on the formalmodels to specify the system and its components,the composition operators, and the conformance relations of the composedsystem vs. the specification.Various behavioural models have been studied in the literature,e.g., finite state machines and automata, omega-automata,process algebras; various forms of synchronous andasynchronous (interleaving/parallel) composition have been considered;the conformance relations include language containment and equality,and notions of simulation.In this paper we give an overview of the problem (a.k.a., the unkown componentproblem, or submodule construction, etc.), and we focus on its reductionto solving equations over languages, as a key technologyfor supporting synthesis of compositional systems.We survey the state-of-art and highlight open problems requiring furtherinvestigation.