scientific article; zbMATH DE number 3311755

Jeffrey D. Ullman, John E. Hopcrofts

Publication date: 1969

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Related Items (only showing first 100 items - show all)

Finite automata-models for the investigation of dynamical systems ⋮ When is a pair of matrices mortal? ⋮ The grammar of mammalian brain capacity ⋮ The full quotient and its closure property for regular languages ⋮ Decision problems for word-hyperbolic semigroups ⋮ An application of Poénaru's ``zipping theory ⋮ Singular propositions, negation and the square of opposition ⋮ Decidable sentences of Church-Rosser congruences ⋮ On some decision questions concerning pushdown machines ⋮ A relationship between two-dimensional finite automata and three-way tape-bounded two-dimensional Turing machines ⋮ Deletion along trajectories ⋮ The language intersection problem for non-recursive context-free grammars ⋮ Automata theory based on quantum logic: Some characterizations ⋮ The aggregation and cancellation techniques as a practical tool for faster matrix multiplication ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Algebraic Myhill-Nerode theorems ⋮ Optimal grids for five-axis machining ⋮ Fixed points avoiding abelian \(k\)-powers ⋮ Block insertion and deletion on trajectories ⋮ Construction of minimal deterministic finite automata from biological motifs ⋮ Algebraic structures of automata ⋮ Finite automata theory with membership values in lattices ⋮ A theory of computation based on unsharp quantum logic: finite state automata and pushdown automata ⋮ The expressive power of analog recurrent neural networks on infinite input streams ⋮ Another approach to the equivalence of measure-many one-way quantum finite automata and its application ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Binary bubble languages and cool-lex order ⋮ Expected distance between terminal nucleotides of RNA secondary structures ⋮ Quasi-rocking real-time pushdown automata ⋮ Hardness of preorder checking for basic formalisms ⋮ Immunity and pseudorandomness of context-free languages ⋮ Multipass automata and group word problems ⋮ Computing power of Turing machines in the framework of unsharp quantum logic ⋮ A shrinking lemma for indexed languages ⋮ A lower bound technique for the size of nondeterministic finite automata ⋮ The element distinctness problem on one-tape Turing machines ⋮ Partial derivatives of regular expressions and finite automaton constructions ⋮ Monotonic and dual monotonic language learning ⋮ Time lower bounds do not exist for CRCW PRAMs ⋮ Computing with infinitary logic ⋮ Extremal solutions of inequations over lattices with applications to supervisory control ⋮ Quasi-deterministic 0L systems and their representation ⋮ Complexity results for 1-safe nets ⋮ An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata ⋮ Effective category and measure in abstract complexity theory ⋮ Approximately matching context-free languages ⋮ A remark on a paper by A.B. Matos ⋮ Universal computation and other capabilities of hybrid and continuous dynamical systems ⋮ An algebraic approach to hybrid systems ⋮ Completeness results concerning systolic tree automata and E0L languages ⋮ Valuations of languages, with applications to fractal geometry ⋮ Tie-breaking semantics and structural totality ⋮ Results on the use of category theory for the study of lattice-valued finite state machines ⋮ Promise problems solved by quantum and classical finite automata ⋮ Nondeterministic fuzzy automata with membership values in complete residuated lattices ⋮ The virtues of idleness: a decidable fragment of resource agent logic ⋮ Further remarks on DNA overlap assembly ⋮ Two double-exponential gaps for automata with a limited pushdown ⋮ Interactive proof systems and alternating time-space complexity ⋮ Recognising \(k\)-connected hypergraphs in cubic time ⋮ Decision problems and regular chain code picture languages ⋮ Algebraic and calculus query languages for recursively typed complex objects ⋮ Parametric runtime verification is NP-complete and coNP-complete ⋮ On the complexity of queries in the logical data model ⋮ The operation \(\uparrow\) on formal power series ⋮ Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements ⋮ On the complexity of minimizing probabilistic and quantum automata ⋮ Disjunctivity and other properties of sets of pseudo-bordered words ⋮ Rewriting of regular expressions and regular path queries ⋮ Bideterministic automata and minimal representations of regular languages ⋮ A coalgebraic approach to Kleene algebra with tests ⋮ Minimizing finite automata is computationally hard ⋮ Decidability of operation problems for T0L languages and subclasses ⋮ Decision problems for convex languages ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Computational complexity of the problem of tree generation under fine-grained access control policies ⋮ Program equilibrium ⋮ Polynomial time learning of simple deterministic languages via queries and a representative sample ⋮ Survey of polynomial transformations between NP-complete problems ⋮ Structural properties of XPath fragments ⋮ Decidable containment of recursive queries ⋮ On reasoning about structural equality in XML: a description logic approach ⋮ Functions with local state: regularity and undecidability ⋮ Adding symbolic information to picture models: definitions and properties ⋮ On state-alternating context-free grammars ⋮ Avoiding large squares in infinite binary words ⋮ Walks in the quarter plane: Kreweras' algebraic model ⋮ Composing model programs for analysis ⋮ Nondeterministic fuzzy automata ⋮ One-reversal counter machines and multihead automata: revisited ⋮ Accepting networks of genetic processors are computationally complete ⋮ On the complexity of some extended word problems defined by cancellation rules ⋮ A lower bound for probabilistic algorithms for finite state machines ⋮ Basic tree transducers ⋮ Look-ahead on pushdowns ⋮ Partition semantics for relations ⋮ Turing complexity of the ordinals ⋮ Presentations of inverse monoids

This page was built for publication: