Expressiveness of Languages

Jock D. Mackinlay, Michael R. GeneserethAAAI 1984

Abstract

In the field of automated information presentation, selecting the appropriate visual language is critical to ensuring clarity and accuracy. This paper, originally presented by Mackinlay and Genesereth in 1984, formalizes the concept of "expressiveness" for specialized languages like diagrams and charts. By utilizing first-order predicate calculus, the authors provide a logical framework to verify that a visualization states exactly the intended facts while avoiding "accidental lies"—implicit facts that are logically forced by the language's structure but are false in the underlying data.

Introduction: The Challenge of Automated Selection

When building systems to automatically generate dashboards or user interfaces, a central challenge is choosing the right "language" for the data. While general-purpose languages like predicate calculus can express nearly any relationship, they are often dense and difficult for humans to parse quickly. Specialized languages—such as maps, tree diagrams, or nested boxes—offer greater clarity but possess limited "expressive power."

The primary risk in using specialized languages is the generation of Implicit Facts. Many visual metaphors are inherently structured such that stating two facts automatically implies a third. For instance, a language using nested rectangles to denote "part-of" relationships creates a transitive chain.

Figure 2: A nested box diagram illustrating implicit part-of relationships between a car, engine, and piston.

As shown in Figure 2, placing a "Piston" box inside an "Engine" box, which is itself inside a "Car" box, implicitly states that a piston is part of a car. If this implicit fact were false in the real world, the language would be inappropriate for the data. This paper seeks to formalize expressiveness so that automated systems can detect and reject such misleading visualizations.

Formal Methodology

The authors bridge the gap between the "world" (the target facts) and the "message" (the visual representation) using First-Order Predicate Calculus.

  1. Axiomatizing the Language: The physical constraints and conventions of a language are defined using axioms. For example, a "Stack of Blocks" language might include axioms for transitivity and anti-reflexivity.
  2. The Expressibility Algorithm: To determine if a language is suitable for a specific dataset, the system assumes the desired facts are true and all other possible facts are false. It then employs automated deduction (resolution) to check for contradictions between these assumptions and the language's internal axioms.
  3. Implicit Closure and Kernels: The authors define "implicit closure" as the minimal set of facts that must be true for a message to be valid. Conversely, the "Implicit Kernel" is the smallest subset of facts that must be explicitly stated to trigger the correct closure, promoting minimalist design.

Key Insights: Transitivity and Perception

A critical insight of the work is the Danger of Transitivity. Many common visual metaphors, such as nesting or linear ordering, are naturally transitive. If a designer uses a transitive visual language to represent a non-transitive relationship (e.g., "next-to"), the diagram will inevitably "lie" by implying connections that do not exist.

Furthermore, the paper distinguishes between Construction Cost (the effort to create a message) and Perception Cost (the effort for a human to decode it). A "good" language aligns its implicit facts with the logical consequences of the data, thereby reducing the "ink" required to convey complex information.

Results and Logical Validation

The core result is a formal, binary criterion for language selection: a language is either expressible for a set of facts or it is not. The system uses contradiction as a filter to discard inappropriate languages.

Figure 4: A formal proof demonstrating how a contradiction is used to reject an inexpressible language.

Figure 4 illustrates this process using the "LAYERTREE" example. If the language's structure forces a connection (e.g., Connected(FundCS, AdvDB)) that the data explicitly denies, the automated deduction finds a contradiction, allowing the system to automatically reject that visualization method.

Limitations and Future Directions

While groundbreaking, the framework has limitations. The computational complexity of automated resolution may lead to non-termination with recursive axioms, necessitating depth limits. Additionally, the paper focuses on expressiveness (can it be said?) rather than effectiveness (how well is it said?). Future work is needed to define criteria for "pleasing" or "dramatic" presentations and to adapt the framework for dynamic, interactive data environments.

Summary updated

BibTeX
@inproceedings{mackinlay1984expressiveness,
  author = {Jock D. Mackinlay and Michael R. Genesereth},
  title = {{Expressiveness of Languages}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure