Understanding System Specifications Written in Natural Language

TL;DR

This paper introduces PHRAN-SPAN, a natural language interface designed to capture abstract system behavior for digital systems using a restricted English dialect. By translating these specifications into a formal representation (the USC Design Data Structure), it aims to overcome the limitations of existing, overly restrictive specification methods.

What Problem Does This Paper Address?

Describing the behavior of complex digital systems, especially those involving multiple interacting processes, is a significant challenge. Traditional methods often impose strict limitations on how these behaviors can be expressed, making it difficult to capture the full nuance of system design. The authors aim to bridge this gap by enabling system specifications to be written in a more natural, albeit restricted, form of English, thereby making the specification process more accessible and less prone to error.

Methods

The core of the system is the PHRAN-SPAN interface, which comprises two main components:

  • PHRAN (PHrasal Analysis): This component acts as a natural language parser. It uses a knowledge-based approach, storing information as "pattern-concept pairs" (PCPs). These PCPs link phrasal constructs (words, phrases, or even syntactic patterns) to semantic concepts. PHRAN analyzes input sentences by matching these patterns and extracting concepts.
  • SPAN (Specification Analysis): This component takes the concepts generated by PHRAN and constructs an internal representation of the system's design data. It maps these concepts onto the USC Design Data Structure (DDS), a unified representation for design data that includes subspaces for Data Flow, Timing and Sequencing, Structural, and Physical aspects.

The system relies on a restricted English input, meaning users must adhere to a specific vocabulary and grammatical structure. The authors developed a corpus of specifications and a lexicon to support this restricted language. They also employ an intermediate representation loosely based on Conceptual Dependency (CD) to facilitate the translation from English to the formal DDS.

Datasets

The paper describes the creation of a corpus for this natural language interface. This corpus was developed by:

  • Acquiring actual system specifications.
  • Having students write specifications.
  • Constructing additional examples based on a taxonomy of high-level system behavior.

A lexicon of approximately 2000-1 word was also developed as part of this research. No specific datasets for quantitative evaluation are mentioned, but the corpus serves as the basis for the system's knowledge and examples.

Key Insights and Ideas

  • Bridging Natural Language and Formal Design: The primary insight is the feasibility of translating natural language specifications into a formal, machine-readable design representation. This can significantly improve the usability and accessibility of design automation tools.
  • Restricted English as a Sweet Spot: By using a restricted form of English, the system can achieve robust parsing and accurate translation without the overwhelming complexity of full natural language understanding. This offers a practical balance between expressiveness and tractability.
  • Conceptual Dependency as an Intermediate Step: The use of an intermediate representation based on Conceptual Dependency helps in capturing the semantic meaning of sentences before mapping them to the formal DDS. This abstraction layer is crucial for handling variations in sentence structure while preserving the core meaning.
  • The USC Design Data Structure (DDS): The DDS provides a comprehensive framework for representing various aspects of digital system design, including data flow, timing, structure, and physical properties. Its unified nature is key to integrating information from natural language specifications.

Key Results

The paper demonstrates the system's ability to process simple sentences related to basic concepts of digital system behavior, such as:

  • Unidirectional Value Transfer (UVT): Describing data movement from a source to a sink.
  • Temporal Activities (e.g., Causal Temporal Initiation/Termination): Specifying events and their timing.
  • Temporal Constraints (e.g., Single/Dual Temporal Relation): Defining relationships between events.

The system can handle multi-noun sequences and detect ambiguities arising from words with similar lexical stems. The authors provide examples of how sentences like "The cpu transfers the command" are translated into the formal DDS representation. The system is coded in Franz Lisp and runs on a SUN/2 workstation, with typical sentences taking 15-35 CPU seconds to process.

Limitations and Future Work

  • Restricted Input: The system requires input in a specific, restricted English dialect. This is a deliberate choice to manage complexity but limits the naturalness of the interaction.
  • Independent Sentence Processing: PHRAN processes each sentence independently. While fragments of DDS graphs are generated, relating these fragments into a coherent system specification requires a post-processing step, which is not detailed.
  • Ambiguity Resolution: While the system can detect some ambiguities, resolving them often requires additional phrases or context, which the current system may not fully handle.
  • Performance: The processing time of 15-35 CPU seconds per sentence is noted as not optimized.

Future work could involve expanding the lexicon and the set of recognized concepts, improving ambiguity resolution, and developing more sophisticated methods for integrating sentence-level specifications into a complete system design.

Summary updated

BibTeX
@inproceedings{1987understanding,
  title = {{Understanding System Specifications Written in Natural Language}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure