Editing by example
ACM Transactions on Programming Languages and SystemsPublished 1 October 1985Open access
Robert Nix
Citations101
SJR quartileQ2
SJR score0.56
SNIP1.52
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
By developing an editing by example system that solves a useful class of text processing problems, this paper demonstrates that program synthesis is feasible in the domain of text editing.
Abstract
An editing by example system is an automatic program synthesis facility embedded in a text editor that can be used to solve repetitive text editing problems. The user provides the editor with a few examples of a text transformation. The system analyzes the examples and generalizes them into a program that can perform the transformation to the rest of the user's text. This paper presents an overview of the design, analysis, and implementation of a practical editing by example system. It studies the problem of synthesizing a text processing program that generalizes the transformation implicitly described by a small number of input/output examples. A class of text processing programs called gap programs is defined and the problems associated with synthesizing them from examples are examined, leading to an efficient heuristic that provably synthesizes a gap program from examples of its input/output behavior. The editing by example system derived from this analysis has been embedded in a production text editor. By developing an editing by example system that solves a useful class of text processing problems, this work demonstrates that program synthesis is feasible in the domain of text editing.
Keywords
Computer Science
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Information and ControlLanguage identification in the limit
3,569 Citations1967Eric Gold
It was found that theclass of context-sensitive languages is learnable from an informant, but that not even the class of regular languages is learningable from a text.
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Communications of the ACMA linear space algorithm for computing maximal common subsequences
1,108 Citations1975D. S. Hirschberg
The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space and an algorithm is presented which will solve this problem in QuadraticTime and in linear space.
Communications of the ACMA fast algorithm for computing longest common subsequences
692 Citations1977James Hunt, Thomas G. Szymanski
An algorithm for finding the longest common subsequence of two sequences of length n which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match.
Journal of the ACMThe Complexity of Some Problems on Subsequences and Supersequences
614 Citations1978David Maier
It is shown that theyes/no version of the LCS problem is NP-complete for sequences over an alphabet of size 2, and that the yes/no SCS problem isNPcomplete for sequence over an Alphabet of size 5.
Journal of Computer and System SciencesFinding patterns common to a set of strings
607 Citations1980Dana Angluin
The main result is a polynomial-time algorithm for the special case of patterns containing only one variable symbol (possibly occurring several times in the pattern).
EMACS the extensible, customizable self-documenting display editor
317 Citations1981Richard Stallman
The organization of the EMACS system is described, emphasizing the way in which extensibility is achieved and used.
Lecture notes in computer sciencePolynomial time inference of extended regular pattern languages
160 Citations1983Takeshi Shinohara
This paper considers polynomial time inference from positive data for the class of extended regular pattern languages which are sets of all strings obtained by substituting any (possibly empty) constant string, instead of non-empty string.
Pygmalion: A Computer program to Model and Stimulate Creative Thought
153 Citations1975David Canfield Smith
ACM Computing SurveysInteractive Editing Systems: Part I
122 Citations1982Norman Meyrowitz, Andries van Dam
A comprehensive and systematic view of the features of typical systems, highlighting substantive similarities and differences is provided, with emphasis on user-level rather than implementation-level considerations.
A high-level approach to computer document formatting
113 Citations1980Brian K. Reid
The document-formatting language Scribe was designed to provide a simple, portable language in which document formatting could be specified; the Scribe compiler was written to process that language into finished documents.
Elsevier eBooksA SURVEY OF RESULTS IN GRAMMATICAL INFERENCE
87 Citations1972Alan W. Biermann, Jerome A. Feldman
T: a dialect of Lisp or LAMBDA
82 Citations1982Jonathan Rees, Norman I. Adams
The T project is an experiment in language design and implementation that tests the thesis developed by Steele and Sussman that Scheme may be used as the basis for a practical programming language of exceptional expressive power and that implementations of Scheme could perform better than other Lisp systems, and competitively with implementations of programming languages.
IEEE Transactions on Systems Man and CyberneticsGrammatical Inference: Introduction and Survey - Part II
74 Citations1975King‐Sun Fu, Taylor L. Booth
The problem of inferring a stochastic grammar to model the behavior of an information source is introduced and techniques for carrying out the inference process are presented for a class of Stochastic finite-state and context-free grammars.
Experience with an applicative string processing language
36 Citations1980James H. Morris, Eric E. Schmidt +1 more
The major conclusions are: Applicative programming can be made more natural through the use of built-in iterative operators and post-fix notation and Clever evaluation strategies can make applicative programming more computationally efficient.
A session with Tinker
34 Citations1980Henry Lieberman, Carl Hewitt
This paper presents a demonstration of the current implementation of Tinker, an experimental interactive programming system which integrates program testing with program design and constructs a procedure for the general case from sample calculations.
Z - the 95% program editor
34 Citations1981Steven R. Wood
This paper describes a text-oriented display editor called Z, which considerably simplifies the design of the editor and presents the user with a simple but powerful model of program structure.
ACM Computing SurveysInteractive Editing Systems: Part II
29 Citations1982Norman Meyrowitz, Andries van Dam
This article surveys the state of the art of computer-based interactwe editing systems, covering line echtors, screen editors, interactive editor/formatters, structure editors, syntax-directed editors, and commercial word-processing editors.
Editing by example
28 Citations1984Robert Nix
An editing by example system derived from an efficient heuristic that provably synthesizes a gap program from examples of its input/output behavior is embedded in a production text editor.
Communications of the ACMA CRT editing system
27 Citations1972Edgar T. Irons, Frans M. Djorup
A text-editing and manipulation program that operates from low-cost cathode-ray tube entry and display stations with keyboard and 13 function buttons is described.
Software Practice and ExperienceTools: An environment for time‐shared computing and programming
5 Citations1983John Ellis, Nathaniel Mishkin +2 more
The Yale Tools environment provides integrated modern computing facilities to a mixed group of programmers and users on time‐shared machines for systems and applications programming, word‐processing and university business.