scientific article; zbMATH DE number 3428547
From MaRDI portal
zbMath0272.68054MaRDI QIDQ5180413
Richard E. Stearns, Philip Lewis, Juris Hartmanis
Publication date: 1970
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
The theory of languages, An optimal lower bound for nonregular languages, Space-efficient recognition of sparse self-reducible languages, Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs, On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes, Lower bounds on communication overlap of networks, Unnamed Item, Proofs of proximity for context-free languages and read-once branching programs, On regular realizability problems for context-free languages, The theory of languages, Remarks on languages acceptable in log log n space, There are no fully space constructible functions between log log n and log n, Unnamed Item, Unnamed Item, Constructing small tree grammars and small circuits for formulas, Optimal node ranking of trees, The language intersection problem for non-recursive context-free grammars, A space efficient algorithm for the monotone planar circuit value problem, Conjunctive and Boolean grammars: the true general case of the context-free grammars, A simulation result for the auxiliary pushdown automata, Tree-size bounded alternation, Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions, \(\varepsilon\)-productions in context-free grammars, On the complexity of regular-grammars with integer attributes, Linear-space recognition for grammars with contexts, If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n, Two-way automata and length-preserving homomorphisms, Space complexity in on-line computation, A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines, Properties that characterize LOGCFL, Space bounded computations: Review and new separation results, Decreasing the bandwidth of a transition matrix, Cut Elimination for Shallow Modal Logics, A note on two-way probabilistic automata, Alternating space is closed under complement and other simulations for sublogarithmic space, WCS-analysis of the context-sensitive, On tape-bounded complexity classes and multihead finite automata, On iterated hairpin completion, An observation on time-storage trade off, Space bounds for processing contentless inputs, The tape-complexity of context-independent developmental languages, Storage requirements for deterministic polynomial time recognizable languages, A characterization of the power of vector machines, Membership for growing context-sensitive grammars is polynomial, Two dynamic programming algorithms for which interpreted pebbling helps, Bracket-languages are recognizable in logarithmic space, Node listings for reducible flow graphs, Economy of description by parsers, DPDA's, and PDA's, On inverse deterministic pushdown transductions, How to walk your dog in the mountains with no magic leash, Lower bounds on space complexity for contextfree recognition, On the space complexity of recursive algorithms, Multihead two-way probabilistic finite automata, Some classes of languages in \(NC^ 1\), Some notes on strong and weak log log n space complexity, Circuits over PP and PL, Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Tape-reversal bounded Turing machine computations, Regular Realizability Problems and Context-Free Languages, Dynamic data structures for timed automata acceptance, A framework for solving VLSI graph layout problems, The alternation hierarchy for sublogarithmic space is infinite, The recursion-theoretic structure of complexity classes, Size-depth tradeoffs for Boolean formulae, (Semi)alternating stack automata
