Introduction to Automata Theory, Languages and Computation

By John E. Hopcroft, Jeffrey D. Ullman. 1979

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Grammar Variational Autoencoder (2017, background): “For more background on context free grammars and automata theory, see e.g. Hopcroft et al. (2006).”
Head-Driven Statistical Models for Natural Language Parsing (2003, positive): “Following Hopcroft and Ullman (1979), we deﬁne a context-free grammar G as a 4-tuple ( N , Σ , A , R ) , where N is a set of nonterminal symbols, Σ is an alphabet, A is a distinguished start symbol in N , and R is a ﬁnite set of rules, in which each rule is of the form X → β for some X ∈ N , β ∈ (…”
Learning by Abstraction: The Neural State Machine (2019, background): “ction 6.1, where we provide greater detail and additional information. 3 The Neural State Machine The Neural State Machine is a graph-based network that simulates the computation of a ﬁnite automaton [35], and is explored here in the context of VQA, where we are given an image and a question and ask”
Extraction of rules from discrete-time recurrent neural networks (1996, background): “In general, however, these distinctions are not significant because of the subsequent standard minimization algorithm (Hopcroft & Ullmann, 1979 ).”
Planning algorithms (2006, methodology): “An interesting connection lies between the ideas of this chapter and the theory of finite automata, which is part of the theory of computation (see [465, 892]).”
Finiteness results for modular curves of genus at least 2 (2002, methodology): “particular, taking G= 2, we ﬁnd that a C-modular hyperelliptic curve has genus at most 17. 5. Computability 5.1. The meaning of computable. “Computable” will mean computable by a Turing machine. (See [31] for a deﬁnition of Turing machine.) To give a precise sense to each statement in our introducti”
The Gremlin graph traversal machine and language (invited talk) (2015, background): “Automata are studied in computer science to understand the minimal structural and behavioral requirements necessary for some “abstract machine” to perform a particular type of computation if it were to be physically built or modeled in another machine powerful enough to simulate its behavior [8].”
A survey of computational complexity results in systems and control (2000, methodology): “For textbook treatments, we refer the reader to Minsky (1967), Aho, Hopcroft and Ullman (1974), Garey and Johnson (1979), Hopcroft and Ullman (1979), Davis (1982) and Papadimitriou (1994).”
A Characterization of the Entropies of Multidimensional Shifts of Finite Type (2007, methodology): “nted as a Turing machine, and it is generally accepted that any eﬀective computation can be performed by a Turing machine; this is Church’s thesis. For background and basic facts on this subject, see [12]. Let Xbe the SFT constructed in section 6, let Rebe the SFT described above and let T be a Turi”
FlashMeta: a framework for inductive program synthesis (2015, methodology): “An efﬁcient algorithm for VSA intersection follows the ideas of automata intersection [11].”
Back in Black: Towards Formal, Black Box Analysis of Sanitizers and Filters (2016, unknown): “This relates to the Myhill-Nerode theorem [21] that, for the above equivalence defined over a language L (i.”
Tool path generation for five-axis NC machining using adaptive space-filling curves (2005, background): “Since the problem is NP-hard (Hopcroft and Ullman 1979), the algorithms for finding the optimal solution are slow and inefficient.”