Publication:5592246
From MaRDI portal
zbMath0196.01701MaRDI QIDQ5592246
Jeffrey D. Ullman, John E. Hopcrofts
Publication date: 1969
Related Items
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, 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, On the complexity of queries in the logical data model, The operation \(\uparrow\) on formal power series, A refined architecture for terminological systems: Terminology = Schema + Views, Comparisons of Parikh's condition to other conditions for context-free languages, Dynamical recognizers: real-time language recognition by analog computers, Algebraic processing of programming languages, PHRASE parsers from multi-axiom grammars, A communication hierarchy of parallel computations, Three-dimensional alternating Turing machines with only universal states, Splicing semigroups of dominoes and DNA, Time-space tradeoffs for algebraic problems on general sequential machines, The string generating power of context-free hypergraph grammars, Average case completeness, Space bounded computations: Review and new separation results, Abstract grammars based on transductions, On multiple context-free grammars, Conflict detection and resolution in a lexical analyzer generator, The complexity of computing the number of strings of given length in context-free languages, Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems, Periodic orbits as the skeleton of classical and quantum chaos, Symbolic dynamics and characterization of complexity, Polynomial-time versus recursive models, Automatic groups and amalgams, Modal functions for concise definition of state machines and products, An analysis of fixed-point queries on binary trees, QRT FIFO automata, breadth-first grammars and their relations, Data-movement-intensive problems: Two folk theorems in parallel computation revisited, Nonuniform complexity and the randomness of certain complete languages, Some properties of space-bounded synchronized alternating Turing machines with universal states only, On the expressive power of finitely typed and universally polymorphic recursive procedures, Inverse monoids and rational Schreier subsets of the free group, Logically defined subsets of \(\mathbb{N}{}^ k\), AUTOMATE, a computing package for automata and finite semigroups, On nonconflicting languages that arise in supervisory control of discrete event systems, On controllability and normality of discrete event dynamical systems, Dynamic programming with convexity, concavity and sparsity, Pattern spectra, substring enumeration, and automatic sequences, The complexity of circuit value and network stability, The invariant problem for binary string structures and the parallel complexity theory of queries, Polynomial-time Abelian groups, A survey of space complexity, Lyapunov exponent spectrum for a generalized coupled map lattice, Fairness, distances and degrees, Extended regular expressions of arbitrary star degrees, Upper bounds on recognition of a hierarchy of non-context-free languages, A characterization of exponential-time languages by alternating context- free grammars, Relating attribute grammars and lexical-functional grammars, Recursively presented games and strategies, A lower bound for the nondeterministic space complexity of context-free recognition, \(\infty\)-regular temporal logic and its model checking problem, Testing logic programs for local stratification, A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space, On reversal-bounded picture languages, Non-associative parallel prefix computation, The parallel complexity of single rule logic programs, Complexity of logical theories involving coprimality, Complexity in left-associative grammar, Communication for alternating machines, Extensions to Barrington's M-program model, The complexity of matrix transposition on one-tape off-line Turing machines with output tape, The computational complexity of satisfiability of temporal Horn formulas in propositional linear-time temporal logic, Group presentations, formal languages and characterizations of one- counter groups, On the limit set of some universal cellular automata, Computing with graph rewriting systems with priorities, Regular sequence operations and their use in database queries, Verifying identical communicating processes is undecidable, The end of pumping, Decidability of the finiteness of ranges of tree transductions, 2-testability and relabelings produce everything, Bridging across the \(\log(n)\) space frontier, Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, Language complexity of rotations and Sturmian sequences, The ancestor width of grammars and languages, Some undecidability results concerning the property of preserving regularity, Synchronization expressions with extended join operation, On well quasi orders of free monoids, A construction on finite automata that has remained hidden, On deciding some equivalences for concurrent processes, Solving constrained Pell equations, An analysis of Lambek's production machines, Set-driven and rearrangement-independent learning of recursive languages, Unnamed Item, Unnamed Item, Data editing and imputation from a computational point of view, Amalgamated free products of inverse semigroups, VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states, Reversible space equals deterministic space, Annotated fuzzy logic programs, Repetitiveness of languages generated by morphisms, Finite nondeterministic automata: simulation and minimality, On lengths of words in context-free languages, Shuffle and scattered deletion closure of languages, An efficient null-free procedure for deciding regular language membership, Using DNA to solve the bounded Post correspondence problem, Approximate string matching using factor automata, A characterization of local regular languages, Dynamically controlled cooperating/distributed grammar systems, Reasoning about strings in databases, In defense of the maximum entropy inference process, Bounds in the propagation of selection into logic programs, The infimal prefix-closed and observable superlanguage of a given language, The calculi of emergence: Computation, dynamics and induction, Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines, A note on two-dimensional probabilistic Turing machines, A probabilistic approach to navigation in Hypertext, Characterization of realizable space complexities, The word problem for nilpotent inverse monoids, Bayesian estimation and the Kalman filter, Stability of discrete linear inclusion, Combinatorial representation of invariants of a soliton cellular automaton, A note on measures of fuzziness applied to nonmonotonic fuzzy propositional logic, Artin groups of extra-large type are biautomatic, Arity and alternation in second-order logic, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, On the splicing operation, Regularity of splicing languages, Independent parallelism in finite copying parallel rewriting systems, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, Synchronization paradigm for protocol testing under multiparty configuration, Problem solving during artificial selection of self-replicating loops, The inclusion problem for some subclasses of context-free languages, A model for deadlock detection based on automata and languages theory, A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly, On free inverse monoid languages, Normal forms for phrase-structure grammars, On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group, On quasi orders of words and the confluence property, Transcendence of binomial and Lucas' formal power series, \(d\)-minimal languages, On computation with pulses, Deterministic generalized automata, Exact performance equivalence: An equivalence relation for stochastic automata, On the computational completeness of context-free parallel communicating grammar systems, Feasible graphs with standard universe, An inequality for non-negative matrices, Temporal connectives versus explicit timestamps to query temporal databases, Regular path queries with constraints, Cut and paste, On deciding trace equivalences for processes, The utilization of fuzzy sets in the recognition of imperfect strings, A description of dynamic behavior for compilers based on object oriented modeling, Regular expressions into finite automata, Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\), The word problem of inverse monoids presented by one idempotent relator, Transformations of one-dimensional cellular automaton rules by translation-invariant local surjective mappings, Nondeterministics circuits, space complexity and quasigroups, The state complexities of some basic operations on regular languages, Fluctuation spectroscopy, A comparative classification of complexity measures, Synthesis of real time acceptors, Decentralized state feedback control of discrete event systems, Synchronized tree automata, On 1-inkdot alternating Turing machines with small space, Turbulent pattern bases for cellular automata, A pumping lemma and the structure of derivations in the boundary NLC graph languages, The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm, Nonuniform learnability, Canonical positions for the factors in paperfolding sequences, On the effects of noise and speed on computations, The complexity of optimizing finite-state transducers, Complex systems, complexity measures, grammars and model-inferring, On sparse languages \(L\) such that \(LL= \Sigma^*\), Graph groups are biautomatic, A note on the complexity of deciding bisimilarity of normed unary processes, Language equations over a one-letter alphabet with union, concatenation and star: A complete solution, On the solvability of domino snake problems, The complexity of connectivity problems on context-free graph languages, A note on multi-inkdot nondeterministic Turing machines with small space, Computational depth and reducibility, Computability with low-dimensional dynamical systems, On recursive bounds for the exceptional values in speed-up, On termination of one rule rewrite systems, Regularity and locality in \(k\)-terminal graphs, Invariant sets for substitution, Computing over the reals with addition and order, The generating power of boundary NLC graph grammars and cycle graphs, Periodic sets of integers, Universality of a reversible two-counter machine, On the computational power of dynamical systems and hybrid systems, The simple dynamics of super Turing theories, A family of universal recurrent networks, Complexity results for two-way and multi-pebble automata and their logics, On path equivalence of nondeterministic finite automata, About the \(p\)-paperfolding words, A polynomial algorithm for deciding bisimilarity of normed context-free processes, Lower bounds for one-way probabilistic communication complexity and their application to space complexity, Finite automata and ordinals, The complexity of PDL with interleaving, On the language of primitive words, Efficient simulations by a biased coin, VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states, Fuzzy semantic analysis and formal specification of conceptual knowledge, The isomorphism conjecture holds and one-way functions exist relative to an oracle, The bounded degree problem for eNCE graph grammars, Deciding true concurrency equivalences on safe, finite nets, Recursion theoretic characterizations of complexity classes of counting functions, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate, Reachability analysis of dynamical systems having piecewise-constant derivatives, The validation of SGML content models, Deterministic automata. Simulation, universality and minimality, Generating grammars for SGML tagged texts lacking DTD, Language-theoretic complexity of disjunctive sequences, On the sequentiality of the successor function, Complexity and categoricity, The single loop representations of regular languages, Growing context-sensitive languages and Church-Rosser languages, Logical description of context-free graph languages, On projective and separable properties, A hierarchy of eNCE families of graph languages, On the power of alternation on reversal-bounded alternating Turing machines with a restriction, Automaticity. II: Descriptional complexity in the unary case, Alternation on cellular automata, Dynamic constraints and object migration, On the computational power of self-stabilizing systems, On computational complexity of contextual languages, Pushdown automata with bounded nondeterminism and bounded ambiguity, A temporal logic for real-time partial ordering with named transactions, From regular expressions to DFA's using compressed NFA's, Permutations generated by token passing in graphs, Restrictions and representations of vector controlled concurrent system behaviours, Monadic logic programs and functional complexity, The set of reversible \(90/150\) cellular automata is regular, Quantum automata and quantum grammars, Realtime subshifts, Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
