scientific article; zbMATH DE number 3664335

Authors John Hopcroft, Jeffrey D. Ullman

Publication date 1979

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cited in

(only showing first 100 items - show all)

Some algebraic properties of measure-once two-way quantum finite automata
Weakly regular quantum grammars and asynchronous quantum automata
On the dynamics and recursive properties of multidimensional symbolic systems
Don't care words with an application to the automata-based approach for real addition
Anyone but him: the complexity of precluding an alternative
State complexity of basic operations on suffix-free regular languages
The Parikh counting functions of sparse context-free languages are quasi-polynomials
Extended multi bottom-up tree transducers
Applications of automata and graphs: Labeling-operators in Hilbert space. I
Prediction, retrodiction, and the amount of information stored in the present
Maximum likelihood analysis of algorithms and data structures
Tests for the LR-, LL-, and LC-regular conditions
The undecidability of self-embedding for term rewriting systems
Depth-first iterative-deepening: An optimal admissible tree search
Complete problems for space bounded subclasses of NP
Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
Test sets for morphisms with bounded delay
On one-one polynomial time equivalence relations
On two problems related to cancellativity
Computation theory of cellular automata
Complete problems in the first-order predicate calculus
String-matching cannot be done by a two-head one-way deterministic finite automaton
Control and data driven execution of logic programs: A comparison
Toward a quantitative theory of self-generated complexity
Complexity of certain decision problems about congruential languages
Continuous optimization problems and a polynomial hierarchy of real functions
Microeconomic foundations of cyclical irregularities or chaos
Monoids with disjunctive identity and their codes
An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
On the continued fraction representation of computable real numbers
A comparison of polynomial time completeness notions
Identification of pattern languages from examples and queries
On the bit complexity of distributed computations in a ring with a leader
Algorithms for the compilation of regular expressions into PLAs
Hierarchies of one-way multihead automata languages
Recognizing safety and liveness
Social choice and computational complexity
Computing power series in polynomial time
Programming simultaneous actions using common knowledge
Polynomial terse sets
Parallel complexity of logical query programs
Intractable problems in reversible cellular automata
The word and generator problems for lattices
Complexity, combinatorial group theory and the language of palutators
On characterizations of the class PSPACE/poly
On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observation
Complexity classes without machines: on complete languages for UP
Promise problems complete for complexity classes
Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
Collapsing degrees
Implication of clauses is undecidable
On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
Modular supervisory control of discrete-event systems
A measure of relativized space which is faithful with respect to depth
Dominoes and the complexity of subclasses of logical theories
Pseudo-natural algorithms for finitely generated presentations of monoids and groups
Complexity theory of parallel time and hardware
Synthesis of communicating process skeletons from temporal-spatial logic specifications
An unpredictability approach to finite-state randomness
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
[[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
Approximate matching of regular expressions
Fairness in context-free grammars under every choice-strategy
An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group
Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
A transformation system for generating description languages of chain code pictures
Characterization and closure properties of linear \(\omega\)-languages
On translations of temporal logic of actions into monadic second-order logic
On XRAM and PRAM models, and on data-movement-intensive problems
Localized planning with action-based constraints
Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
Algebraic structures in categorial grammar
Reachability in live and safe free-choice Petri nets is NP-complete
Formulae relating controllability, observability, and co-observability
Langages sur des alphabets infinis
The complexity of decision problems for finite-turn multicounter machines
On the complexity of simple arithmetic expressions
Thue congruences and the Church-Rosser property
A uniform approach to obtain diagonal sets in complexity classes
Physics of selective systems: Computation and biology
When is a monoid a group? The Church-Rosser case is tractable
Quadratic automata
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
Reduction and covering of infinite reachability trees
Algorithms for graph problems on BNLC structured garphs
Learning regular languages from counterexamples
On sets polynomially enumerable by iteration
On the degree of ambiguity of finite automata
Strong and robustly strong polynomial-time reducibilities to sparse sets
The complexity of Grigorchuk groups with application to cryptography
The implementation of a protocol using automata
Language in action
Alternation with a pebble
Minimizing the number of transitions with respect to observation equivalence
Knowledge representation for mathematical discovery: Three experiments in graph theory
The complexity of problems involving structurally bounded and conservative Petri nets
On p-creative sets and p-completely creative sets
Iterated stack automata and complexity classes
Learning in the presence of partial explanations

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3862379)