Logspace and logtime leaf languages
From MaRDI portal
Publication:1817219
DOI10.1006/inco.1996.0071zbMath0864.68057OpenAlexW2080456897MaRDI QIDQ1817219
Pierre McKenzie, Denis Thérien, Birgit Jenner
Publication date: 23 February 1997
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1996.0071
Related Items
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ A characterization of the leaf language classes ⋮ Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ Unambiguous computations and locally definable acceptance types ⋮ Gap-languages and log-time complexity classes ⋮ On balanced versus unbalanced computation trees ⋮ Succinct circuit representations and leaf language classes are basically the same concept ⋮ On the acceptance power of regular languages ⋮ Leaf languages and string compression ⋮ Unnamed Item ⋮ Dot operators ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Relating polynomial time to constant depth ⋮ Nondeterministic \(NC^1\) computation ⋮ LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY ⋮ SELF-SPECIFYING MACHINES ⋮ A reducibility for the dot-depth hierarchy
This page was built for publication: Logspace and logtime leaf languages