Michael A. Harrison

Last updated
Michael A. Harrison
Born
Philadelphia, PA, U.S.A.
Alma mater University of Michigan
Known forformal language theory, Harrison-Ruzzo-Ullman model
Scientific career
Thesis Combinatorial Problems in Boolean Algebras and Applications to the Theory of Switching (1963)
Doctoral advisor Harvey Garner
Doctoral students Jim Gray, Oscar Ibarra
Website www.cs.berkeley.edu/~harrison

Michael A. Harrison is a computer scientist, in particular a pioneer in the area of formal languages.

Contents

Biography

Michael A. Harrison (born in Philadelphia, Pennsylvania, U.S.) studied electrical engineering and computing for BS and MS at the Case Institute of Technology, and then received a PhD from the University of Michigan in Communication Sciences. He was assistant professor from 1963 to 1966 at the University of Michigan, and then joined the faculty of the E.E. Dept at the University of California at Berkeley, where he was an associate professor from 1966 to 1971, and a full professor from 1971 to 1994. [1]

In the 1960s, he worked with Sheila Greibach, Gene Rose, Ed Spanier, and Joe Ullian in a research group formed and led by Seymour Ginsburg, dedicated to formal language theory and the foundations of Computer Science. The work that came out of this group distinguished Computer Science theory from other fields. It also brought the field of formal language theory to bear on programming language research. [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

In 1975, he developed the HRU security model (named after its authors Harrison, Ruzzo, Ullman), an operating system level computer security model dealing with the integrity of access rights in the system. [12] [13] [14] [15] With his Ph.D. student Pehong Chen at Berkeley, [16] [17] [18] [19] he founded the "Gain Technology" company (acquired by Sybase in 1992). [20]

Currently, he is professor emeritus and also professor in the graduate school at Berkeley. [1]

Personal life

Harrison is married to Susan L. Graham, the Pehong Chen Distinguished Professor Emerita in the Computer Science Division of the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. [21]

Related Research Articles

In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).

In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form if all of its production rules are of the form:

Alfred Vaino Aho is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming.

<span class="mw-page-title-main">Richard E. Stearns</span> American computer scientist

Richard Edwin Stearns is an American computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory". In 1994 he was inducted as a Fellow of the Association for Computing Machinery.

<span class="mw-page-title-main">Computational learning theory</span> Theory of machine learning

In computer science, computational learning theory is a subfield of artificial intelligence devoted to studying the design and analysis of machine learning algorithms.

Sheila Adele Greibach is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los Angeles, and notable work include working with Seymour Ginsburg and Michael A. Harrison in context-sensitive parsing using the stack automaton model.

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non-empty context-free language admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions.

An operator precedence grammar is a kind of grammar for formal languages.

In automata theory, a deterministic pushdown automaton is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.

In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.

The HRU security model is an operating system level computer security model which deals with the integrity of access rights in the system. It is an extension of the Graham-Denning model, based around the idea of a finite set of procedures being available to edit the access rights of a subject on an object . It is named after its three authors, Michael A. Harrison, Walter L. Ruzzo and Jeffrey D. Ullman.

Seymour Ginsburg was an American pioneer of automata theory, formal language theory, and database theory, in particular; and computer science, in general. His work was influential in distinguishing theoretical Computer Science from the disciplines of Mathematics and Electrical Engineering.

Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automata.

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs.

<span class="mw-page-title-main">Nested stack automaton</span>

In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks. Like a stack automaton, a nested stack automaton may step up or down in the stack, and read the current symbol; in addition, it may at any place create a new stack, operate on that one, eventually destroy it, and continue operating on the old stack. This way, stacks can be nested recursively to an arbitrary depth; however, the automaton always operates on the innermost stack only.

In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.

In computer science, in particular in the field of formal language theory, an abstract family of languages is an abstract mathematical notion generalizing characteristics common to the regular languages, the context-free languages and the recursively enumerable languages, and other families of formal languages studied in the scientific literature.

In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words, so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that area.

Richard Emil Ladner is an American computer scientist known for his contributions to both theoretical computer science and assistive technology. Ladner is a professor emeritus at the University of Washington.

References

  1. 1 2 Long Vita at Harrison's Home page
  2. ↑ Abiteboul, S.; Hull, R.; Vianu, V. (March 2005), "In memory of Seymour Ginsburg, 1928–2004", ACM SIGMOD Record, 34 (1): 5, doi:10.1145/1058150.1058152
  3. ↑ Seymour Ginsburg; Sheila A. Greibach; Michael A. Harrison (1967). "One-Way Stack Automata". J. ACM. 14 (2): 389–418. doi: 10.1145/321386.321403 .
  4. ↑ Seymour Ginsburg; Sheila A. Greibach; Michael A. Harrison (1967). "Stack Automata and Compiling". J. ACM. 14 (1): 172–201. doi: 10.1145/321371.321385 .
  5. ↑ Seymour Ginsburg; Michael A. Harrison (1967). "Bracketed Context-Free Languages". J. Comput. Syst. Sci. 1 (1): 1–23. doi:10.1016/s0022-0000(67)80003-5.
  6. ↑ Jim Gray; Michael A. Harrison; Oscar H. Ibarra (1967). "Two-Way Pushdown Automata". Information and Control. 11 (1–2): 30–70. doi:10.1016/s0019-9958(67)90369-5.
  7. ↑ Hervé Gallaire; Jim Gray; Michael A. Harrison; Gabor T. Herman (1968). "Infinite Linear Sequential Machines". J. Comput. Syst. Sci. 2 (4): 381–419. doi:10.1016/s0022-0000(68)80035-2.
  8. ↑ Michael A. Harrison; Oscar H. Ibarra (1968). "Multi-Tape and Multi-Head Pushdown Automata". Information and Control. 13 (5): 433–470. doi: 10.1016/s0019-9958(68)90901-7 .
  9. ↑ Seymour Ginsburg; Michael A. Harrison (1968). "One-Way Nondeterministic Real-Time List-Storage Languages". J. ACM. 15 (3): 428–446. doi: 10.1145/321466.321475 .
  10. ↑ Seymour Ginsburg; Michael A. Harrison (1968). "On the Elimination of Endmarkers". Information and Control. 12 (2): 103–115. doi:10.1016/s0019-9958(68)90221-0.
  11. ↑ Seymour Ginsburg; Michael A. Harrison (1970). "On the Closure of AFL under Reversal". Information and Control. 17 (4): 395–409. doi: 10.1016/s0019-9958(70)80035-3 .
  12. ↑ Michael A. Harrison; Walter L. Ruzzo; Jeffrey D. Ullman (1975). "On Protection in Operating System". Proc. 5th Symp. on Operating System Principles (SOSP). pp. 14–24.
  13. ↑ Michael A. Harrison (1975). "On Models of Protection in Operating Systems". In Jirí Becvár (ed.). 4th Symposium on Mathematical Foundations of Computer Science (MFCS). LNCS. Vol. 32. pp. 46–60.
  14. ↑ Harrison, Michael A.; Ruzzo, Walter L.; Ullman, Jeffrey D. (August 1976). "Protection in Operating Systems". Communications of the ACM. 19 (8): 461–471. CiteSeerX   10.1.1.106.7226 . doi:10.1145/360303.360333.
  15. ↑ Michael A. Harrison (1985). "Theoretical Issues Concerning Protection in Operating Systems". Advances in Computers Volume 24. pp. 61–100. doi:10.1016/s0065-2458(08)60365-4. ISBN   9780120121243.{{cite book}}: |journal= ignored (help)
  16. ↑ Pehong Chen; John Coker; Michael A. Harrison; Jeffrey W. McCarrell; Steve Procter (1986). "The VorTeX Document Preparation Environment". In Jacques Désarménien (ed.). 2nd Eur. Conf. on TeX for Scientific Documentation. pp. 45–54.
  17. ↑ Pehong Chen; Michael A. Harrison; Jeffrey W. McCarrell; John Coker; Steve Procter (1986). "An Improved User Environment for TeX". In Jacques Désarménien (ed.). 2nd Eur. Conf. on TeX for Scientific Documentation. pp. 32–44.
  18. ↑ Pehong Chen; Michael A. Harrison (1988). "Index Preparation and Processing". Software: Practice and Experience. 18 (9): 897–915. CiteSeerX   10.1.1.169.9719 . doi:10.1002/spe.4380180907.
  19. ↑ Pehong Chen; Michael A. Harrison (1988). "Multiple Representation Document Development". IEEE Computer. 21 (1): 15–31. doi:10.1109/2.222114.
  20. ↑ Bloomberg Businessweek
  21. ↑ Susan L Graham and Helen Meyer Named Co-Chairs of Cal Performances at UC Berkeley
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.