A semantically-derived subset of English for hardware verification

Alexander Holt, Ewan KleinACL 1999 · DOI

Abstract

This paper addresses the "formalization gap" in hardware engineering—the cognitive and technical distance between natural language design specifications and the formal temporal logic required for automated verification. The authors propose a structured hierarchy of "Controlled English" subsets, ranging from literal transliterations of logic to context-dependent natural language. By aligning linguistic complexity with the semantic constraints of Computation Tree Logic (CTL), this framework provides a roadmap for developing intuitive yet mathematically precise natural language interfaces for model checking tools.

Introduction

In modern hardware design, model checking is a critical technique for ensuring circuit correctness. However, its adoption is hindered by the requirement that designers express specifications in formalisms like Computation Tree Logic (CTL). While CTL is mathematically rigorous, it is notoriously difficult for humans to author and debug. Conversely, natural language (English) is the intuitive medium for designers but is often too ambiguous for automated tools.

Previous attempts to bridge this gap often failed by attempting to map broad, unrestricted English into logic. Many common English constructions simply cannot be expressed in CTL, leading to translation failures. The authors propose a different approach: restricting English to specific subsets that are "semantically derived" from the target logic, ensuring that every valid sentence in the subset has a guaranteed, unambiguous translation into CTL.

A Hierarchy of Controlled English

The core contribution of this work is a four-level hierarchy of English sublanguages, categorized by their linguistic complexity and their relationship to the underlying formal logic.

The proposed hierarchy of Controlled English levels, ranging from pure CTL transliteration to full semantic representation.

Level 1: Transliteration ($L_1$ and $L_1^+$)

The most basic level, $L_1$, involves a literal, one-to-one mapping of CTL operators into English. For example, the formula $AG(p \rightarrow AF q)$ might be rendered as "Globally, if $p$ is high, then eventually $q$ will be high." While mathematically sound, $L_1$ often feels robotic. $L_1^+$ improves upon this by adding synonyms and minor syntactic variations (e.g., "always" instead of "globally") without increasing the underlying semantic complexity.

Examples of CTL formulas and their corresponding English senses in the L1 subset.

Level 2: Compositional Indirect Semantics ($L_2$)

Level $L_2$ introduces "ontologically rich" terms such as pulse, edge, rise, or fall. These terms do not exist as primitives in pure CTL, which is state-based. However, they can be algorithmically expanded into complex CTL formulas. For instance, a "rising edge" of a signal $i$ can be defined as a state where $i$ is low followed immediately by a state where $i$ is high. $L_2$ allows designers to speak the language of transitions while the system compiles these concepts down into state-based logic.

Level 3: Non-compositional Indirect Semantics ($L_3$)

$L_3$ represents the highest level of complexity, where the meaning of a sentence depends on the specific domain or protocol context. In a handshaking protocol, a term like "eventually acknowledged" might imply specific timing constraints or intermediate signal changes that require domain-specific inference to translate correctly. This level remains largely theoretical and requires sophisticated inference engines.

Methodology and Empirical Basis

To ground their hierarchy in real-world practice, the authors collected a corpus of approximately 100 sentences from qualified hardware engineers. These participants were shown timing diagrams—visual representations of signal transitions over time—and asked to describe the observed behavior in natural English. This dataset provided the "ground truth" for the linguistic constructions designers naturally use, such as referring to signal edges and pulses, which directly informed the development of the $L_2$ level.

Technically, the authors implemented a prototype tool called ctl2eng using a Definite Clause Grammar (DCG) to map CTL formulas to $L_1$ English. They also developed a context-free grammar for $L_2$, demonstrating that "rich" hardware concepts can be systematically mapped to an "Extended CTL."

Key Insights and Future Work

A primary insight of the paper is that English is "richer" than CTL because it naturally describes transitions and events, whereas CTL describes sequences of states. By identifying this ontological gap, the authors were able to define the $L_2$ level as a bridge that "compiles" event-based language into state-based logic.

While the framework provides a clear formalization roadmap, several limitations remain. The current $L_2$ prototype simplifies many linguistic nuances, such as subject-verb agreement and the use of anaphora (e.g., using "it" to refer back to a previously mentioned signal). Future work aims to incorporate "specification patterns"—recurring structural templates in hardware design—to further reduce ambiguity and enhance the naturalness of the controlled language.

Summary updated

BibTeX
@inproceedings{holt1999semantically,
  author = {Alexander Holt and Ewan Klein},
  title = {{A semantically-derived subset of English for hardware verification}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1999},
  doi = {10.3115/1034678.1034747},
}
Figure