Component-Based Design by Solving Language Equations

Tiziano Villa

doi:10.1109/JPROC.2015.2450937

Component-Based Design by Solving Language Equations

2015-11-01

10

PRE

AI

DOI：10.1109/JPROC.2015.2450937

Original

Original request for help

Save

Abstract

En 中文

An important step in the design of a complex system is its decomposition into 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 component that when combined with the known part of the system (the context) satisfies a given specification. This problem arises in several applications ranging from sequential synthesis to the design of discrete controllers. There are different formulations of the problem, depending on the formal models to specify the system and its components, the composition operators, and the conformance relations of the composed system versus the specification. Various behavioral models have been studied in the literature, e.g., finite state machines and automata, omega-automata, process algebras; various forms of synchronous and asynchronous (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 component problem, or submodule construction, etc.), and we focus on its reduction to solving equations over languages, as a key technology for supporting synthesis of compositional systems. We survey the state-of-art and highlight open problems requiring further investigation.

Keywords:

Component-based design

decomposition of finite automata and state machines

finite automata and state machines

parallel and synchronous language equations

synthesis of unknown component

Component-Based Design by Solving Language Equations

Abstract

AI Summary

Journal

Organization