66 results on '"Alfred V. Aho"'
Search Results
2. Learning Java in a New York City immigrant engineer retraining program
- Author
-
Alfred V. Aho, Larisa Ackerman, Fred L. Fontaine, and Suzanna Schmeelk
- Subjects
Java ,Computer science ,Computational thinking ,05 social sciences ,Psychology of programming ,Retraining ,050301 education ,02 engineering and technology ,020204 information systems ,ComputingMilieux_COMPUTERSANDEDUCATION ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics education ,Student learning ,Set (psychology) ,Construct (philosophy) ,0503 education ,computer ,Curriculum ,computer.programming_language - Abstract
This research explores the psychology of programming and the pedagogical environment in a certificate granting urban immigrant engineer retraining program in New York City. The program is aimed at teaching under-represented immigrant engineer students to learn how to program in the Java programming language. The programming concepts and the fostered pedagogical environment were implemented in three-hour evening sessions over 15 weeks in which the students were encouraged to develop programming communities while working on computational thinking concept strands. The research findings that we report are threefold. First, we report on how we fostered building programming concepts into the curriculum into a set of activities specifically designed for an immigrant engineer retraining program with students ranging in backgrounds. We found that at that the program curriculum must be flexible enough for student learning regardless of the fact that a student may miss sessions. Second, we report on how an effective pedagogical environment, which fosters student-centered learning, was promoted so that the students could construct their own meanings of the programming concepts. Third, we report on implementation strategies unique to a retraining program, such as specific environmental constraints as well as how sessions were partitioned into components that fostered computational thinking while learning Java. Our findings provide unique insights into intervention constraints for an urban retraining program which can be used to guide and inform further retraining computer learning program research. more...
- Published
- 2017
- Full Text
- View/download PDF
Catalog
3. Defending android applications availability
- Author
-
Alfred V. Aho and Suzanna Schmeelk
- Subjects
Open source ,Computer science ,System level ,Malware ,Denial-of-service attack ,Android application ,Static analysis ,Android (operating system) ,Android device ,computer.software_genre ,Computer security ,computer - Abstract
There are over a billion devices running the Android operating system. It is being used globally in personal, public, private and government organizations. Device and application availability, often overlooked in research, is a huge component to globally maintaining healthy applications and personal communications. Published research into Android application availability threats and vulnerabilities is limited and incomplete. At most, published research on static analysis techniques used to prevent and thwart Android availability denial of service has been discussed as an aside in only a few papers. To fill the research gap in understanding, this paper examines Android device denial of service techniques both at a system level and at an application level. Our research quantitatively examines applications' availability risks. These risks are used to develop Android mitigation techniques for application denial of service scenarios and inform the development of our third contribution produced from this research. In our third contribution, we introduce a novel open source Android application, the App-Nanny, as a watchdog application to help ensure that applications are playing fair on the device. Lastly, we give insights into future mobile availability testing which includes developing a ChaosMonkeyApp helping to ensure hardening and resiliency in both devices and their running applications. more...
- Published
- 2017
- Full Text
- View/download PDF
4. Computation and Computational Thinking
- Author
-
Alfred V. Aho
- Subjects
Theoretical computer science ,General Computer Science ,Human-based evolutionary computation ,Computer science ,Semantics (computer science) ,Computation ,Model of computation ,Symbolic-numeric computation ,Interactive evolutionary computation ,Term (time) ,Human-based computation - Abstract
We recommend using the term Computation in conjunction with a well-defined model of computation whose semantics is clear and which matches the problem being investigated. Computer science already has a number of useful clearly defined models of computation whose behaviors and capabilities are well understood. We should use such models as part of any definition of the term computation. However, for new domains of investigation where there are no appropriate models it may be necessary to invent new formalisms to represent the systems under study. more...
- Published
- 2012
- Full Text
- View/download PDF
5. A layered software architecture for quantum computing design tools
- Author
-
Krysta M. Svore, Alfred V. Aho, Isaac L. Chuang, Andrew W. Cross, and Igor L. Markov
- Subjects
General Computer Science ,business.industry ,Computer science ,Computation ,Design flow ,computer.software_genre ,Computer architecture ,High-level programming language ,Quantum system ,Computer Science::Programming Languages ,Computer Aided Design ,Quantum algorithm ,Electronic design automation ,Compiler ,Software engineering ,business ,Software architecture ,computer ,Quantum computer - Abstract
Compilers and computer-aided design tools are essential for fine-grained control of nanoscale quantum-mechanical systems. A proposed four-phase design flow assists with computations by transforming a quantum algorithm from a high-level language program into precisely scheduled physical actions. more...
- Published
- 2006
- Full Text
- View/download PDF
6. Teaching the compilers course
- Author
-
Alfred V. Aho
- Subjects
System programming ,Compiler construction ,Programming language ,Computer science ,Foundation (evidence) ,General Materials Science ,Compiler ,computer.software_genre ,Mutually exclusive events ,computer ,Course (navigation) - Abstract
I have always enjoyed teaching the compilers course. Compiler design is a beautiful marriage of theory and practice -it is one of the first major areas of systems programming for which a strong theoretical foundation has developed that is now routinely used in practice. I am a strong believer in Donald Knuth’s credo: “Theory and practice are not mutually exclusive; they are intimately connected. They live together and support each other.” [5] more...
- Published
- 2008
- Full Text
- View/download PDF
7. Emerging opportunities for theoretical computer science
- Author
-
Catherine C. McGeoch, Richard M. Karp, Alfred V. Aho, Pavel A. Pevzner, Christos H. Papadimitriou, David S. Johnson, and S. Rao Kosaraju
- Subjects
Distributed Computing Environment ,Multidisciplinary ,Theoretical computer science ,Exploit ,Management science ,Section (archaeology) ,Computer science ,Information access ,Algorithm engineering ,Context (language use) ,Applied research ,Field (computer science) - Abstract
The principles underlying this report can be summarized as follows:1. A strong theoretical foundation is vital to computer science.2. Theory can be enriched by practice.3. Practice can be enriched by theory.4. If we are guided by (2) and (3), the value, impact, and funding of theory will be enhanced.In order to achieve a greater synergy between theory and application, and to sustain and expand on the remarkable successes of Theory of Computing (TOC), we consider it essential to increase the impact of theory on key application areas. This requires additional financial resources in support of theory, and closer interaction between theoreticians and researchers in other areas of computer science and in other disciplines.The report does not make a detailed assessment of the overall state of theoretical computer science or fully chronicle the achievements of this field. Instead, it has the specific objective of recommending ways to harness these remarkable achievements for the solution of challenging problems emerging from new developments such as the information superhighway.Section 1 describes the events leading up to this report and delineates the report's objectives. Section 2 establishes the context for the report. It traces the history of TOC, describes the impact that TOC has achieved in the areas of core theory and fundamental algorithms, points out the differences between these areas and application-oriented theory, and calls for an intensified effort to bring the methods of TOC to bear on applications. It then goes on to define the four main categories into which our recommen- dations fall: building bridges between theory and applications, algorithm engineering, communication, and education. Section 3 discusses some specific opportunities for stimulating interactions between TOC and applied areas. Section 4 proposes an applied research initiative, Information Access in a Globally Distributed Environment , which identifies an exciting current technological area that we believe presents challenging opportunities for excellent theoretical work. Section 5 proposes a second applied research initiative, The Algorithmic Stockroom , that would exploit and extend the body of theoretical knowledge in the field of algorithms. Section 6 proposes a broadening in graduate education with two purposes in mind: to better prepare theoreticians to interact creatively with practitioners, and to provide future practitioners with the background they will need to benefit from this exchange. more...
- Published
- 1997
- Full Text
- View/download PDF
8. Families of Graphs and Digraphs
- Author
-
Alfred V. Aho
- Subjects
Discrete mathematics ,Graph drawing ,Computer science ,Adjacency list - Published
- 2013
- Full Text
- View/download PDF
9. Computer Science : The Hardware, Software and Heart of It
- Author
-
Edward K. Blum, Alfred V Aho, Edward K. Blum, and Alfred V Aho
- Subjects
- Computer science
- Abstract
Computer Science: The Hardware, Software and Heart of It focuses on the deeper aspects of the two recognized subdivisions of Computer Science, Software and Hardware. These subdivisions are shown to be closely interrelated as a result of the stored-program concept. Computer Science: The Hardware, Software and Heart of It includes certain classical theoretical computer science topics such as Unsolvability (e.g. the halting problem) and Undecidability (e.g. Godel's incompleteness theorem) that treat problems that exist under the Church-Turing thesis of computation. These problem topics explain inherent limits lying at the heart of software, and in effect define boundaries beyond which computer science professionals cannot go beyond. Newer topics such as Cloud Computing are also covered in this book. After a survey of traditional programming languages (e.g. Fortran and C++), a new kind of computer Programming for parallel/distributed computing is presented using the message-passing paradigm which is at the heart of large clusters of computers. This leads to descriptions of current hardware platforms for large-scale computing, such as clusters of as many as one thousand which are the new generation of supercomputers. This also leads to a consideration of future quantum computers and a possible escape from the Church-Turing thesis to a new computation paradigm. The book's historical context is especially helpful during this, the centenary of Turing's birth. Alan Turing is widely regarded as the father of Computer Science, since many concepts in both the hardware and software of Computer Science can be traced to his pioneering research. Turing was a multi-faceted mathematician-engineer and was able to work on both concrete and abstract levels. This book shows how these two seemingly disparate aspects of Computer Science are intimately related. Further, the book treats the theoretical side ofComputer Science as well, which also derives from Turing's research. Computer Science: The Hardware, Software and Heart of It is designed as a professional book for practitioners and researchers working in the related fields of Quantum Computing, Cloud Computing, Computer Networking, as well as non-scientist readers. Advanced-level and undergraduate students concentrating on computer science, engineering and mathematics will also find this book useful. more...
- Published
- 2011
10. Ubiquity symposium: Computation and Computational Thinking
- Author
-
Alfred V. Aho
- Subjects
Ninth ,Computer science ,business.industry ,Computation ,Computational thinking ,General Medicine ,Artificial intelligence ,business ,GeneralLiterature_MISCELLANEOUS - Abstract
In this ninth piece to the Ubiquity symposium discussing What is computation? Alfred V. Aho shares his views about the importance of computational thinking in answering the question. --Editor
- Published
- 2011
- Full Text
- View/download PDF
11. An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours
- Author
-
M.U. Uyar, Alfred V. Aho, A.T. Dahbura, and D. Lee
- Subjects
Route inspection problem ,Finite-state machine ,Theoretical computer science ,Computational complexity theory ,Computer science ,Graph (abstract data type) ,Observability ,Directed graph ,Electrical and Electronic Engineering ,Conformance testing ,Algorithm ,Protocol (object-oriented programming) - Abstract
A method for generating test sequences for checking the conformance of a protocol implementation to its specification is described. A rural Chinese postman tour problem algorithm is used to determine a minimum-cost tour of the transition graph of a finite-state machine. It is shown that, when the unique input/output sequence (UIO) is used in place of the more cumbersome distinguishing sequence, both the controllability and observability problems of the protocol testing problem are addressed, providing an efficient method for computing a test sequence for protocol conformance testing. > more...
- Published
- 1991
- Full Text
- View/download PDF
12. CERBERUS: Tracing Requirements to Source Code Using Information Retrieval, Dynamic Analysis, and Program Analysis
- Author
-
Giuliano Antoniol, Yann-Gaël Guéhéneuc, Alfred V. Aho, and Marc Eaddy
- Subjects
Source code ,Dependency (UML) ,Information retrieval ,Java ,Computer science ,media_common.quotation_subject ,Software maintenance ,Tracing ,JavaScript ,Program analysis ,computer ,computer.programming_language ,media_common ,TRACE (psycholinguistics) - Abstract
The concern location problem is to identify the source code within a program related to the features, requirements, or other concerns of the program. This problem is central to program development and maintenance. We present a new technique called prune dependency analysis that can be combined with existing techniques to dramatically improve the accuracy of concern location. We developed CERBERUS, a potent hybrid technique for concern location that combines information retrieval, execution tracing, and prune dependency analysis. We used CERBERUS to trace the 360 requirements of RHINO, a 32,134 line Java program that implements the ECMAScript international standard. In our experiment, prune dependency analysis boosted the recall of information retrieval by 155% and execution tracing by 104%. Moreover, we show that our combined technique outperformed the other techniques when run individually or in pairs. more...
- Published
- 2008
- Full Text
- View/download PDF
13. Debugging Aspect-Enabled Programs
- Author
-
Marc Eaddy, Weiping Hu, Julian Burger, Alfred V. Aho, and Paddy McDonald
- Subjects
Computer science ,Programming language ,media_common.quotation_subject ,Interactive debugging ,Software_PROGRAMMINGTECHNIQUES ,computer.software_genre ,Fault detection and isolation ,Control flow ,Algorithmic program debugging ,Debugging ,Software_SOFTWAREENGINEERING ,Program behavior ,Software_PROGRAMMINGLANGUAGES ,Weaving ,Programmer ,computer ,media_common - Abstract
The ability to debug programs composed using aspect-oriented programming (AOP) techniques is critical to the adoption of AOP. Nevertheless, many AOP systems lack adequate support for debugging, making it difficult to diagnose faults and understand the program's composition and control flow. We present an AOP debug model that characterizes AOP-specific program composition techniques and AOP-specific program behaviors, and relates them to the AOP-specific faults they induce. We specify debugging criteria that we feel all AOP systems should support and compare how several AOP systems measure up to this ideal. We explain why AOP composition techniques, particularly dynamic and binary weaving, hinder source-level debugging, and how results from related research on debugging optimized code help solve the problem. We also present Wicca, the first dynamic AOP system to support full source-level debugging. We demonstrate how Wicca's powerful interactive debugging features allow a programmer to quickly diagnose faults in the base program behavior or AOP-specific behavior. more...
- Published
- 2007
- Full Text
- View/download PDF
14. Software and the future of programming languages
- Author
-
Alfred V. Aho
- Subjects
Social software engineering ,Multidisciplinary ,Resource-oriented architecture ,business.industry ,Computer science ,Programming language ,Software development ,History, 20th Century ,computer.software_genre ,Software framework ,Component-based software engineering ,Software construction ,Package development process ,Programming Languages ,business ,computer ,Software ,Forecasting - Abstract
Although software is the key enabler of the global information infrastructure, the amount and extent of software in use in the world today are not widely understood, nor are the programming languages and paradigms that have been used to create the software. The vast size of the embedded base of existing software and the increasing costs of software maintenance, poor security, and limited functionality are posing significant challenges for the software R&D community. more...
- Published
- 2004
15. Columbia Digital News System. An environment for briefing and search over multimedia information
- Author
-
Dragomir R. Radev, Kazi Atif-Uz Zaman, Kathleen R. McKeown, Alfred V. Aho, John R. Smith, and Shih-Fu Chang
- Subjects
Focus (computing) ,Distributed database ,Multimedia ,Computer science ,business.industry ,Suite ,Interoperability ,Information technology ,Digital library ,computer.software_genre ,Track (rail transport) ,Automatic summarization ,World Wide Web ,business ,computer - Abstract
In this paper we describe an ongoing research project called the Columbia Digital News System. The goal of this project is to develop a suite of effective interoperable tools with which people can find relevant information (text, images, video, and structured documents) from distributed sources and track it over a period of time. Our initial focus is on the development of a system with which researchers, journalists, and students can keep track of current news events in specific areas. more...
- Published
- 2002
- Full Text
- View/download PDF
16. A front row seat to Communications ' editorial transformation
- Author
-
Georg Gottlob and Alfred V. Aho
- Subjects
Transformation (function) ,General Computer Science ,Computer science ,business.industry ,Telecommunications ,business ,Front (military) - Published
- 2014
- Full Text
- View/download PDF
17. Columbia digital news project: an environment for briefing and search over multimedia information
- Author
-
Dragomir R. Radev, John R. Smith, Kazi Atif-Uz Zaman, Kathleen R. McKeown, Shih-Fu Chang, and Alfred V. Aho
- Subjects
World Wide Web ,Focus (computing) ,Computer science ,Suite ,Interoperability ,Multimedia information ,Library and Information Sciences ,Track (rail transport) ,Relevant information ,Automatic summarization - Abstract
In this paper we describe an ongoing research project called the Columbia Digital News Project. The goal of this project is to develop a suite of effective interoperable tools with which people can find relevant information (text, images, video, and structured documents) from distributed sources and track it over a period of time. Our initial focus is on the development of a system with which researchers, journalists, and students can keep track of current news events in specific areas. more...
- Published
- 1998
- Full Text
- View/download PDF
18. Accessing information from globally distributed knowledge repositories (extended abstract)
- Author
-
Alfred V. Aho
- Subjects
World Wide Web ,Knowledge management ,Distributed knowledge ,Computer science ,business.industry ,business - Published
- 1996
- Full Text
- View/download PDF
19. Feature interactions in the global information infrastructure
- Author
-
Nancy Griffeth and Alfred V. Aho
- Subjects
World Wide Web ,Global information infrastructure ,Converged infrastructure ,Feature (computer vision) ,Computer science ,Information infrastructure ,Global information system - Published
- 1995
- Full Text
- View/download PDF
20. Algorithms for Finding Patterns in Strings
- Author
-
Alfred V. Aho
- Subjects
Data processing ,Theoretical computer science ,Computer science ,Lexical analysis ,Information processing ,String searching algorithm ,Rewriting ,String metric ,Approximate string matching ,Algorithm ,Substring - Abstract
Publisher Summary This chapter discusses the algorithms for solving string-matching problems that have proven useful for text-editing and text-processing applications. String pattern matching is an important problem that occurs in many areas of science and information processing. In computing, it occurs naturally as part of data processing, text editing, term rewriting, lexical analysis, and information retrieval. Many text editors and programming languages have facilities for matching strings. In biology, string-matching problems arise in the analysis of nucleic acids and protein sequences, and in the investigation of molecular phylogeny. String matching is also one of the central and most widely studied problems in theoretical computer science. The simplest form of the problem is to locate an occurrence of a keyword as a substring in a sequence of characters, which is called the input string. For example, the input string queueing contains the keyword ueuei as a substring. Even for this problem, several innovative, theoretically interesting algorithms have been devised that run significantly faster than the obvious brute-force method. more...
- Published
- 1990
- Full Text
- View/download PDF
21. Bounds on the size and transmission rate of communications protocols
- Author
-
Jeffrey D. Ullman, A.D. Wyner, Mihalis Yannakakis, and Alfred V. Aho
- Subjects
Protocol (science) ,business.industry ,Computer science ,Transmission rate ,Communications system ,Topology ,Nonlinear Sciences::Cellular Automata and Lattice Gases ,Automaton ,Computational Mathematics ,Computational Theory and Mathematics ,Modeling and Simulation ,Modelling and Simulation ,Communications protocol ,business ,Computer Science::Formal Languages and Automata Theory ,Communication channel ,Computer network ,Computer Science::Information Theory - Abstract
Using a pair of finite-state automata to model the transmitter-receiver protocol in a data communications system, we derive lower bounds on the size of automata needed to achieve reliable communication across an error-prone channel. We also show that, at the cost of increasing the size of the automata, a transmission rate close to the theoretical maximum can be achieved. more...
- Published
- 1982
- Full Text
- View/download PDF
22. Code Generation for Expressions with Common Subexpressions
- Author
-
Jeffrey D. Ullman, Alfred V. Aho, and S. C. Johnson
- Subjects
Dead code ,Computer science ,Expression (mathematics) ,Systematic code ,Artificial Intelligence ,Hardware and Architecture ,Control and Systems Engineering ,Code (cryptography) ,Code generation ,Redundant code ,Heuristics ,Algorithm ,Time complexity ,Software ,Information Systems - Abstract
This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their worst-case behavior is analyzed. For one register machines, an optimal code generation algorithm is given whose time complexity is linear in the size of an expression and exponential only in the amount of sharing. more...
- Published
- 1977
- Full Text
- View/download PDF
23. Bounds on the Complexity of the Longest Common Subsequence Problem
- Author
-
Jeffrey D. Ullman, Daniel S. Hirschberg, and Alfred V. Aho
- Subjects
Discrete mathematics ,Computer science ,String (computer science) ,Longest increasing subsequence ,Function (mathematics) ,Upper and lower bounds ,Function problem ,Combinatorics ,Longest common subsequence problem ,Quadratic equation ,Artificial Intelligence ,Hardware and Architecture ,Control and Systems Engineering ,Longest alternating subsequence ,Software ,Decision tree model ,Information Systems ,Mathematics - Abstract
The problem of finding a longest common subsequence of two strings is discussed. This problem arises in data processing applications such as comparing two files and in genetic applications such as studying molecular evolution. The difficulty of computing a longest common subsequence of two strings is examined using the decision tree model of computation, in which vertices represent “equal - unequal” comparisons. It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings. A general lower bound as a function of the ratio of alphabet size to string length is derived. The case where comparisons between symbols of the same string are forbidden is also considered and it is shown that this problem is of linear complexity for a two-symbol alphabet and quadratic for an alphabet of three or more symbols. more...
- Published
- 1976
- Full Text
- View/download PDF
24. LR Parsing
- Author
-
Alfred V. Aho and S. C. Johnson
- Subjects
General Computer Science ,LR parser ,business.industry ,Computer science ,Artificial intelligence ,computer.software_genre ,business ,computer ,Natural language processing ,Canonical LR parser ,Theoretical Computer Science - Published
- 1974
- Full Text
- View/download PDF
25. Algorithms and computational complexity
- Author
-
Alfred V. Aho
- Subjects
Computational learning theory ,Computer science ,business.industry ,Computer programming ,Designtheory ,Asymptotic computational complexity ,Worst-case complexity ,Probabilistic analysis of algorithms ,General Medicine ,Computational problem ,Computational resource ,business ,Algorithm - Abstract
Computer programming was and, in many cases, still is an art rather than a science. Programs are often written without the benefit of any design theory, analysis techniques, or awareness of what others in the field have done. Recently, however, a systematic body of knowledge concerning the design, analysis, and implementation of computer algorithms has begun to emerge. This paper highlights some current developments in this field and shows how proper design techniques can lead to order-of-magnitude improvements in program performance. more...
- Published
- 1977
- Full Text
- View/download PDF
26. Dynamic Memories with Rapid Random and Sequential Access
- Author
-
Jeffrey D. Ullman and Alfred V. Aho
- Subjects
Sequential access memory ,Distributed shared memory ,Hardware_MEMORYSTRUCTURES ,Computer science ,Cache-only memory architecture ,Uniform memory access ,Registered memory ,ComputerApplications_COMPUTERSINOTHERSYSTEMS ,Semiconductor memory ,Parallel computing ,Memory map ,Sequential access ,Theoretical Computer Science ,Non-uniform memory access ,Memory management ,Physical address ,Computational Theory and Mathematics ,Shared memory ,Hardware and Architecture ,Memory architecture ,Interleaved memory ,Software ,Computer memory - Abstract
We propose a new architecture for dynamic memories in which the contents of any cell in memory can be accessed by applying a sequence of two primitive memory operations. The advantage of our memory over previous designs is its fast sequential access. Any word in an n cell memory can be accessed in 0(log n) steps. However, once two consecutive words have been accessed, following words can be accessed in one step per word. more...
- Published
- 1974
- Full Text
- View/download PDF
27. Code generation using tree matching and dynamic programming
- Author
-
Alfred V. Aho, Mahadevan Ganapathi, and Steven W. K. Tjiang
- Subjects
Tree (data structure) ,Generator (computer programming) ,Parsing ,Programming language ,Computer science ,Code generation ,Compiler ,Construct (python library) ,computer.software_genre ,Instruction selection ,computer ,Software ,Blossom algorithm - Abstract
Compiler-component generators, such as lexical analyzer generators and parser generators, have long been used to facilitate the construction of compilers. A tree-manipulation language called twig has been developed to help construct efficient code generators. Twig transforms a tree-translation scheme into a code generator that combines a fast top-down tree-pattern matching algorithm with dynamic programming. Twig has been used to specify and construct code generators for several experimental compilers targeted for different machines. more...
- Published
- 1989
- Full Text
- View/download PDF
28. Efficient string matching
- Author
-
Alfred V. Aho and Margaret J. Corasick
- Subjects
Theoretical computer science ,General Computer Science ,Bitap algorithm ,Computer science ,Boyer–Moore–Horspool algorithm ,String (computer science) ,Commentz-Walter algorithm ,String searching algorithm ,Approximate string matching ,Text string ,Rabin–Karp algorithm ,law.invention ,law ,Aho–Corasick string matching algorithm ,3-dimensional matching ,Suffix automaton ,Pattern matching ,String metric ,Boyer–Moore string search algorithm ,Compressed pattern matching - Abstract
This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10. more...
- Published
- 1975
- Full Text
- View/download PDF
29. Awk — a pattern scanning and processing language
- Author
-
Peter J. Weinberger, Alfred V. Aho, and Brian W. Kernighan
- Subjects
Computer science ,Programming language ,String (computer science) ,Processing ,Relational operator ,computer.software_genre ,Field (computer science) ,Set (abstract data type) ,AWK ,Regular expression ,Line (text file) ,computer ,Software ,computer.programming_language - Abstract
This paper describes the design and implementation of awk, a programming language which searches a set of files for patterns, and performs specified actions upon records or fields of records which match the patterns. Awk makes common data selection and transformation operations easy to express; for example, is a complete awk program that prints all input lines whose length exceeds 72 characters. The program prints each input line with the first field replaced by its logarithm. The program prints all lines in which the first field is different from the first field of the previous line. Patterns may include boolean combinations of regular expressions and of relational operators on strings, numbers, fields, variables, and array elements. Actions may include: the same matching constructions as in patterns; arithmetic and string expressions and assignments; if-else, while, and for statements; formatted output; and multiple output streams. more...
- Published
- 1979
- Full Text
- View/download PDF
30. High level language programming environments
- Author
-
Marvin V. Zelkowitz, John A. Nestor, Alfred V. Aho, Daniel G. Bobrow, Gordon Lyon, John C. Cherniavsky, Susan L. Gerhart, W. Richards Adrion, Terry Straeter, and Thomas E. Cheatham
- Subjects
Programming language ,Functional logic programming ,Computer science ,Reactive programming ,Programming paradigm ,General Medicine ,Fifth-generation programming language ,Programming domain ,computer.software_genre ,First-generation programming language ,computer ,Inductive programming ,Extensible programming - Published
- 1981
- Full Text
- View/download PDF
31. Optimal partial-match retrieval when fields are independently specified
- Author
-
Alfred V. Aho and Jeffrey D. Ullman
- Subjects
Sequence ,Optimality criterion ,Computer science ,Hash function ,Listing (computer) ,computer.software_genre ,Bin ,Field (computer science) ,Zero (linguistics) ,Set (abstract data type) ,Data mining ,Algorithm ,computer ,Information Systems - Abstract
This paper considers the design of a system to answer partial-match queries from a file containing a collection of records, each record consisting of a sequence of fields. A partial-match query is a specification of values for zero or more fields of a record, and the answer to a query is a listing of all records in the file whose fields match the specified values. A design is considered in which the file is stored in a set of bins. A formula is derived for the optimal number of bits in a bin address to assign to each field, assuming the probability that a given field is specified in a query is independent of what other fields are specified. Implications of the optimality criterion on the size of bins are also discussed. more...
- Published
- 1979
- Full Text
- View/download PDF
32. Maintaining cross references in manuscripts
- Author
-
Alfred V. Aho and Ravi Sethi
- Subjects
troff ,Sequence ,Variable (computer science) ,Programming language ,Computer science ,String (computer science) ,Line (text file) ,computer.software_genre ,computer ,Software - Abstract
Authors face the tedious bookkeeping problem of maintaining the consistency of references to figures, citations, and other numbered entities in successive drafts of a manuscript. If a figure is added to or deleted from the manuscript, the numbers of all subsequent figures must be adjusted, along with the references to these figures. In this note, we show how the UNIX commands grep, awk, and sed can be used to create a simple and flexible reference assembler that automatically maintains the consistency of cross references in manuscripts. 1. A REFERENCE ASSEMBLER First, prepare a source text for the manuscript in which each reference is symbolic, such as ‘‘Fig. _Output_’’ or ‘‘Page _Section2_’’, rather than an explicit numeric designation, such as ‘‘Fig. 3’’ or ‘‘Page 3’’. Following Scribe [8], the name of a numbered entity will be called a tag, and a symbolic page number a page label. Tags represent numbers that are independent of the layout of a manuscript: The number associated with a tag depends on how many other tag definitions precede it in the source text, and can be deduced by looking at the source text alone. Page numbers, on the other hand, depend on the final layout of the text. Section 4 describes a mechanism for handling page labels using the troff text-formatter. In the source text, define each tag by a line of the form .@tag countervariable tagname In a tag definition, @tag is a distinctive keyword, countervariable is an identifier for an integer variable, and tagname is a string used as a tag. The . in the first position of the definition indicates that the line is not part of the actual text of the manuscript. Tag definitions and references can appear anywhere in the source text, but the definitions will be numbered in the order in which they appear. The initial value of a counter variable is zero. Whenever a new tag definition is encountered, the underlying counter variable is incremented and the incremented value of this counter variable is associated with the new tag name. We can create as many different classes of symbolic references as we wish by using a distinct counter variable for each class. In this way, citations, figures, examples, sections, footnotes, and the like can have their own sequence numbers. Example 1. Figure 1 shows the contents of a file source containing the text of a short manuscript. Lines 3, 6, 8, and 11 contain the tags _Alice_ and _Huckleberry_. Lines 7 and 10 contain the corresponding tag definitions .@tag CITE _Alice_ .@tag CITE _Huckleberry_ using the counter variable CITE to keep track of citation numbers. To create the assembled output in which the symbolic references are replaced by numeric ones, execute the UNIX commands in Fig. 2. These commands constitute a complete reference assembler for tags. The grep-awk pipe in the first three lines of Fig. 2 creates in the file sedscript a sequence of sed instructions that will associate the numbers 1 and 2 with the tags _Alice_ and _Huckleberry_, respectively. Invoked with this script, the sed command in the last line of Fig. 2 replaces all occurrences more...
- Published
- 1988
- Full Text
- View/download PDF
33. Time and tape complexity of pushdown automaton languages
- Author
-
Jeffrey D. Ullman, Alfred V. Aho, and John E. Hopcroft
- Subjects
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES ,Nested word ,Theoretical computer science ,Deterministic context-free language ,Computer science ,Deterministic context-free grammar ,Context-free language ,General Engineering ,Pushdown automaton ,Multitape Turing machine ,Embedded pushdown automaton ,Automaton ,Deterministic pushdown automaton ,Nondeterministic algorithm ,Turing machine ,symbols.namesake ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Deterministic automaton ,symbols ,Two-way deterministic finite automaton ,Engineering(all) ,Computer Science::Formal Languages and Automata Theory - Abstract
A n algorithm is presented which will determine whether any string w in Z*, of length n, is contained in a language L C Z* defined by a two-way nondeterministic pushdown automaton, This algorithm re- quires time n 3 when implemented on a random access computer. It re- quires n 4 time and n 2 tape when implemented on a multitape Turing machine. If the pushdown automaton is deterministic, the algorithm re- quires n ~ time on a random access computer and n 2 log n time on a mul- titape Turing machine. I. INTRODUCTION A pushdown store is a list in which information can be accessed only on a last-in first-out principle of operation. The use of pushdown stores is an important technique in the construction of compilers and other language processing devices. Of particular interest from both practical and theoretical considera- tions is how the time and memory required to process a language is func- tionally related to the length of the input sentence under consideration. In this paper we consider languages defined by pushdown store systems and we investigate how much time and memory is needed in order to de- termine whether an arbitrary input sentence belongs or does not belong to some language in this class. To obtain analytical results, a pushdown automaton (PDA for short) will be used as the model of a pushdown store system. There are four types of pushdown automaton depending on whether the automaton is deterministic or nondeterministie and whether it moves one or two ways on the input. We will use the following abbreviations for pushd0wn au- * Currently at Cornell University, Ithaca, New York. 186 more...
- Published
- 1968
- Full Text
- View/download PDF
34. The theory of languages
- Author
-
Jeffrey D. Ullman and Alfred V. Aho
- Subjects
Programming language ,Computer science ,General Mathematics ,Comparison of multi-paradigm programming languages ,String (computer science) ,Abstract family of languages ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Second-generation programming language ,Ontology language ,computer.software_genre ,Cone (formal languages) ,Theoretical Computer Science ,Computational Theory and Mathematics ,Formal language ,Computer Science::Programming Languages ,computer ,Natural language - Abstract
Let ~ be a finite set of symbols, or alphabet. Define ~* to be the set of all finite length strings of symbols in X, including ~, the string of length 0. A language is a subset of X*, for some alphabet ~. Clearly, the natural languages and programming languages are languages in the formal sense. The theory of languages is concerned with the description of languages, their recognition and processing. A language may contain an infinite number of strings, so at the least, one needs a finite description of the language. Particular types of finite descriptions will yield useful properties of the languages they define, especially when the class of languages they define is "small" (i.e., not every language of conceivable interest is described). If C is the class of languages defined by a certain type of description, one would like to know whether membership in C is preserved under various operations. One would like to know that the languages in class C could be recognized quickly and simply, especially if one were attempting to develop a compiling system for a language or languages in C. Also useful are characterizations of languages in C, so one can tell easily if a given language is in class C. Finally, one wants algorithms, if they exist, to answer certain questions about the languages in C, such as: "Is string w in language L?" In this article, we will give the principal methods of describing languages and the principal results concerning each method. more...
- Published
- 1968
- Full Text
- View/download PDF
35. Nested Stack Automata
- Author
-
Alfred V. Aho
- Subjects
Stack (abstract data type) ,Nested stack automaton ,Artificial Intelligence ,Hardware and Architecture ,Control and Systems Engineering ,Computer science ,Parallel computing ,Embedded pushdown automaton ,Software ,Information Systems ,Automaton - Published
- 1969
- Full Text
- View/download PDF
36. Weak and Mixed Strategy Precedence Parsing
- Author
-
Alfred V. Aho, Jeffrey D. Ullman, and Peter J. Denning
- Subjects
Parsing ,business.industry ,Computer science ,Speech recognition ,computer.software_genre ,Strategy ,Artificial Intelligence ,Hardware and Architecture ,Control and Systems Engineering ,Artificial intelligence ,business ,computer ,Software ,Natural language processing ,Information Systems - Published
- 1972
- Full Text
- View/download PDF
37. A Minimum Distance Error-Correcting Parser for Context-Free Languages
- Author
-
Thomas G. Peterson and Alfred V. Aho
- Subjects
Chomsky normal form ,String-to-string correction problem ,Parsing ,General Computer Science ,Syntax (programming languages) ,Computer science ,General Mathematics ,Speech recognition ,Context-free language ,String (computer science) ,computer.software_genre ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Syntax error ,Arithmetic ,computer ,Symbol (formal) - Abstract
We assume three types of syntax errors can debase the sentences of a language generated by a context-free grammar: the replacement of a symbol by an incorrect symbol, the insertion of an extraneous symbol, or the deletion of a symbol. We present an algorithm that will parse any input string to completion finding the fewest possible number of errors. On a random access computer the algorithm requires time proportional to the cube of the length of the input. more...
- Published
- 1972
- Full Text
- View/download PDF
38. Optimization of Straight Line Programs
- Author
-
Alfred V. Aho and Jeffrey D. Ullman
- Subjects
Set (abstract data type) ,Algebraic laws ,General Computer Science ,Computer science ,General Mathematics ,Code (cryptography) ,Order (ring theory) ,Straight-line program ,Program optimization ,Algorithm - Abstract
We provide a set of transformations capable of transforming a straight line program into any other equivalent one assuming no algebraic laws hold. We then show that optimization of straight line code under “reasonable” cost criteria can always be accomplished by applying sequences of these transformations in a prescribed order. more...
- Published
- 1972
- Full Text
- View/download PDF
39. Error detection in precedence parsers
- Author
-
Alfred V. Aho and Jeffrey D. Ullman
- Subjects
Parsing ,Computer science ,General Mathematics ,computer.software_genre ,Theoretical Computer Science ,Matrix (mathematics) ,Computational Theory and Mathematics ,Symbol (programming) ,Theory of computation ,Error detection and correction ,Algorithm ,computer ,Equivalence (measure theory) ,SIMPLE algorithm - Abstract
We consider methods by which a precedence matrix may be modified without severely degrading the error-detecting capability of a parser utilizing the matrix. Two different definitions of “the same” error detection capability are considered. The first, called “exact equivalence”, permits only useless parts of the precedence matrix to be modified. The second, called simply “equivalence”, allows the modified matrix to perform some reductions, but never to shift an input symbol, after the original has detected an error. We give necessary and sufficient conditions for a modified precedence parser to be equivalent or exactly equivalent to the canonical parser. We then consider the interesting case where the modification is caused by replacing the precedence matrix by linear precedence functions. A simple algorithm to find (if they exist) exactly equivalent linear precedence functions for a given precedence matrix is presented. more...
- Published
- 1973
- Full Text
- View/download PDF
40. Characterizations and extensions of pushdown translations
- Author
-
Alfred V. Aho and Jeffrey D. Ullman
- Subjects
Syntax (programming languages) ,Hierarchy (mathematics) ,Computer science ,Programming language ,General Mathematics ,Existential quantification ,Pushdown automaton ,computer.software_genre ,Embedded pushdown automaton ,Theoretical Computer Science ,Deterministic pushdown automaton ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Computational Theory and Mathematics ,Theory of computation ,computer ,Computer Science::Formal Languages and Automata Theory - Abstract
A device called a pushdown assembler has been recently introduced and has been shown capable of defining exactly the syntax directed translations (SDT's). The output operation of the pushdown assembler can be extended in a natural way to obtain a more powerful device called a type B pushdown assembler (or B-machine). A B-machine can define SDT's more simply and directly than the original pushdown assembler. B-machines can also define many interesting translations which are not SDT's. In this paper the B-machine is defined and compared with the original pushdown assembler. The properties of B-machine translations are investigated and it is shown that, as with SDT's, there exists a natural infinite hierarchy of B-machine translations. more...
- Published
- 1971
- Full Text
- View/download PDF
41. A Technique for Speeding up ${\text{LR}}(k)$ Parsers
- Author
-
Jeffrey D. Ullman and Alfred V. Aho
- Subjects
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Transformation (function) ,Parsing ,General Computer Science ,Programming language ,Computer science ,General Mathematics ,Of the form ,Software_PROGRAMMINGLANGUAGES ,computer.software_genre ,computer - Abstract
We present a new transformation that reduces the size and increases the speed of ${\text{LR}}(k)$ parsers. This transformation can be applied to all ${\text{LR}}(k)$ parsers including those produced by Knuth’s and DeRemer’s techniques. The transformation causes the parser to avoid reductions by productions of the form $A \to B$, where A and B are nonterminals. more...
- Published
- 1973
- Full Text
- View/download PDF
42. A formal approach to code optimization
- Author
-
Jeffrey D. Ullman, Ravi Sethi, and Alfred V. Aho
- Subjects
Theoretical computer science ,Polynomial code ,Dead code ,Processor register ,Computer science ,Loop-invariant code motion ,Locally testable code ,Program optimization ,Computer Graphics and Computer-Aided Design ,Dead code elimination ,Dual code ,Systematic code ,Canonical Huffman code ,Universal code ,Code generation ,Constant-weight code ,Unreachable code ,Redundant code ,Algorithm ,Machine code ,Software - Abstract
We examine from a formal point of view some problems which arise in code optimization and present some of the results which can come from such an approach. Specifically, a set of transformations which characterize optimization algorithms for straight line code is presented. Then we present an algorithm which produces machine code for evaluating arithmetic expressions on machines with N ≥ 1 general purpose registers. We can prove that this algorithm produces optimal code when the cost criterion is the length of machine code generated. more...
- Published
- 1970
- Full Text
- View/download PDF
43. Syntax directed translations and the pushdown assembler
- Author
-
Alfred V. Aho and Jeffrey D. Ullman
- Subjects
Hierarchy (mathematics) ,Syntax (programming languages) ,Grammar ,Computer Networks and Communications ,Programming language ,Computer science ,Applied Mathematics ,Existential quantification ,media_common.quotation_subject ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,computer.software_genre ,Theoretical Computer Science ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Computational Theory and Mathematics ,Computer Science::Logic in Computer Science ,computer ,Computer Science::Formal Languages and Automata Theory ,media_common - Abstract
It is shown that there exists an infinite hierarchy of syntax-directed translations according to the number of nonterminals allowed on the right side of productions of the underlying context-free grammar. A device called the pushdown assembler is defined, and it is shown capable of performing exactly the syntax-directed translations. more...
- Published
- 1969
- Full Text
- View/download PDF
44. Properties of syntax directed translations
- Author
-
Alfred V. Aho and Jeffrey D. Ullman
- Subjects
Discrete mathematics ,Syntax (programming languages) ,Computer science ,Programming language ,Computer Networks and Communications ,Existential quantification ,Applied Mathematics ,Context-free language ,Pushdown automaton ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Type (model theory) ,Context-free grammar ,computer.software_genre ,Syntax-directed translation ,Theoretical Computer Science ,Computational Theory and Mathematics ,Homomorphism ,computer ,Computer Science::Formal Languages and Automata Theory - Abstract
Translations that can be expressed as generalizations of context free grammars and pushdown automata are defined. The types of translations defined are ordered according to power. For each type, certain necessary conditions that a translation be of that type are given. It is shown that T is a simple syntax directed translation if and only if there is a context free language L and homomorphisms h"1 and h"2 such that T={(h"1(w), h"2(w))@?w is in L}. Every syntax directed translation with one input symbol and one output symbol can be defined by a sequential transducer. For every syntax directed translation T, there is a constant c, such that for all w @e in the domain of T, there exists (w, x) in T, with |x|@?c|w|. A context free language is unambiguous if and only if it is the domain of a translation defined by a deterministic pushdown recognizer (pushdown automation with two input tapes). more...
- Published
- 1969
- Full Text
- View/download PDF
45. Optimization of LR(k) parsers
- Author
-
Jeffrey D. Ullman and Alfred V. Aho
- Subjects
Parsing ,Computational Theory and Mathematics ,Computer science ,Simple (abstract algebra) ,Computer Networks and Communications ,Applied Mathematics ,Arithmetic ,Special case ,computer.software_genre ,Algorithm ,computer ,Canonical LR parser ,Theoretical Computer Science - Abstract
Certain techniques for modifying LR(k) parsing tables to decrease their size have been developed by Korenjak [2] and DeRemer [3, 4]. We show that the techniques of the latter can be characterized by two transformations on sets of tables. We then show that the ''simple'' LR(1) method of DeRemer [4] can be considered a special case of Korenjak's method [2]. more...
- Published
- 1972
- Full Text
- View/download PDF
46. Indexed Grammars—An Extension of Context-Free Grammars
- Author
-
Alfred V. Aho
- Subjects
Programming language ,business.industry ,Computer science ,Context-sensitive grammar ,Context-free grammar ,computer.software_genre ,Tree-adjoining grammar ,Indexed language ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Extended Affix Grammar ,Ambiguous grammar ,Artificial Intelligence ,Hardware and Architecture ,Control and Systems Engineering ,Affix grammar ,Indexed grammar ,Artificial intelligence ,business ,computer ,Software ,Natural language processing ,Information Systems - Abstract
A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and decidability results similar to those for context-free languages. The class of languages generated by indexed grammars properly includes all context-free languages and is a proper subset of the class of context-sensitive languages. Several subclasses of indexed grammars generate interesting classes of languages. more...
- Published
- 1968
- Full Text
- View/download PDF
47. Principles of Optimal Page Replacement
- Author
-
Peter J. Denning, Alfred V. Aho, and Jeffrey D. Ullman
- Subjects
Mathematical optimization ,System organization ,Flat memory model ,Computer science ,Parallel computing ,Page replacement algorithm ,Dynamic programming ,Artificial Intelligence ,Hardware and Architecture ,Control and Systems Engineering ,Demand paging ,Paging ,Program behavior ,Software ,Information Systems - Abstract
ABSTP~CT. A formal model is presented for paging algorithms under /-order nonstationary assumptions about program behavior. When processing a program under paging in a given memory, a given paging policy generates a certain (expected) number of page calls, i.e., its "cost." Under usual assumptions about memory system organization, minimum cost is always achieved by a demand paging algorithm. The minimum cost for /-order program behavior assumptions is expressed as a dynamic programming problem whose solution yields an optimal replacement algorithm. Solutions are exhibited in several 0-order cases of interest. Paging algorithms that implement and approximate the minimum cost are discussed. more...
- Published
- 1971
- Full Text
- View/download PDF
48. Special SIGACT issue
- Author
-
Edward K. Blum, P.C. Fischer, and Alfred V. Aho
- Subjects
Computational Theory and Mathematics ,Computer science ,Computer Networks and Communications ,Theory of computing ,Applied Mathematics ,Mathematical economics ,Theoretical Computer Science - Published
- 1974
- Full Text
- View/download PDF
49. How hard is compiler code generation?
- Author
-
Alfred V. Aho and Ravi Sethi
- Subjects
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Compiler construction ,Dead code ,Object code ,Programming language ,Computer science ,Code generation ,Compiler ,Unreachable code ,computer.software_genre ,Code bloat ,computer ,Dead code elimination - Abstract
Over the past two decades great strides have been made in understanding how to design lexical and syntactic analyzers for programming-language compilers. Theory and practice have proceeded to the point where usable lexical and syntactic analyzers can be generated automatically from notations based on regular expressions and context-free grammars [Aho and Ullman (1977), Johnson (1975), Lesk (1975)]. Unfortunately, our understanding of code generation has not kept pace with the developments in the syntactic domain. Recently, however, a number of theoretical results have been obtained which suggest how well and how extensively code generation can be automated. This paper summarizes these results and discusses the problems that still remain to be solved. more...
- Published
- 1977
- Full Text
- View/download PDF
50. Modeling communications protocols by automata
- Author
-
Alfred V. Aho, Mihalis Yannakakis, and Jeffrey D. Ullman
- Subjects
Reliability theory ,Robustness (computer science) ,Computer science ,Distributed computing ,Nonlinear Sciences::Cellular Automata and Lattice Gases ,Information theory ,Communications system ,Error detection and correction ,Communications protocol ,Computer Science::Formal Languages and Automata Theory ,Decoding methods ,Computer Science::Information Theory ,Automaton - Abstract
Using a pair of finite-state automata to model the transmitter-receiver protocol in a data communications system, we derive lower bounds on the size of automata needed to achieve reliable communication across an error-phone channel. We also show that, at the cost of increasing the size of the automata, a transmission rate close to the theoretical maximum can be achieved. more...
- Published
- 1979
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.