Log Space Recognition and Translation of Parenthesis Languages
From MaRDI portal
Publication:4185825
DOI10.1145/322033.322037zbMath0401.68051OpenAlexW1995502606MaRDI QIDQ4185825
Publication date: 1977
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322033.322037
Related Items
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, The complexity of combinatorial problems with succinct input representation, Bi-Lipschitz bijection between the Boolean cube and the Hamming ball, On the Complexity of the Model Checking Problem, The lattice and semigroup structure of multipermutations, Decompositions of nondeterministic reductions, A generalization of Spira's theorem and circuits with small segregators or separators, A space efficient algorithm for the monotone planar circuit value problem, First-Order Model Checking Problems Parameterized by the Model, On truth-table reducibility to SAT, Lower bounds against weakly-uniform threshold circuits, Complexity of DNF minimization and isomorphism testing for monotone formulas, Generic oracles, uniform machines, and codes, The word problem for visibly pushdown languages described by grammars, Strategic reasoning with a bounded number of resources: the quest for tractability, Relativization of questions about log space computability, The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions, Lower bounds on space complexity for contextfree recognition, A combinatorial characterization of smooth LTCs and applications, The Orthogonal Vectors Conjecture for Branching Programs and Formulas, The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments, On strict interpretations of grammar forms, Unnamed Item, The complexity of propositional linear temporal logics in simple cases, Consistency in nondeterministic storage, Space-bounded hierarchies and probabilistic computations, Taming past LTL and flat counter systems
