Nonerasing, counting, and majority over the linear time hierarchy
type: Item
instance of: scholarly article
title: Nonerasing, counting, and majority over the linear time hierarchy
zbMATH Open document ID: 1009.68051
author: Arnaud Durand
author: Malika More
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1853254
MaRDI profile type: Publication
full work available at URL: inco.2001.3084
OpenAlex ID: W2012707656
cites work: On counting problems and the polynomial-time hierarchy
cites work: A machine description and the hierarchy of initial Grzegorczyk classes
cites work: Q3866086
cites work: Sharply bounded alternation and quasilinear time
cites work: Relativized alternation and space-bounded computation
cites work: Nondeterministic stack register machines
cites work: Rudimentary relations and primitive recursion: A toolbox
cites work: ON THE NOTION OF LINEAR TIME COMPUTABILITY
cites work: Linear Time Algorithms and NP-Complete Problems
cites work: Sorting, linear time and the satisfiability problem
cites work: Monadic logical definability of nondeterministic linear time
cites work: Q3826533
cites work: Q5286672
cites work: Small Grzegorczyk classes and limited minimum
cites work: Context-free languages and rudimentary attributes
cites work: Rudimentary Languages and Second‐Order Logic
cites work: On quasilinear-time complexity theory
cites work: Q5628106
cites work: Q3773860
cites work: Q3689182
cites work: Counting $Δ_0$ sets
cites work: Satisfiability Is Quasilinear Complete in NQL
cites work: Theory of Formal Systems. (AM-47)
cites work: The polynomial-time hierarchy
cites work: Complexity classes defined by counting quantifiers
cites work: The Complexity of Enumeration and Reliability Problems
cites work: The complexity of combinatorial problems with succinct input representation
cites work: Rudimentary Predicates and Relative Computation
DOI: 10.1006/INCO.2001.3084
description: scientific article; zbMATH DE number 1853254