Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
type: Item
instance of: scholarly article
title: Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
zbMATH Open document ID: 1204.68098
author: Nutan Limaye
author: Meena Mahajan
author: B. V. Raghavendra Rao
published in: Theory of Computing Systems
publication date: 2010-05-05T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5703835
zbMATH Keywords: bounded-width circuits
zbMATH Keywords: branching programs
zbMATH Keywords: circuit degree
zbMATH Keywords: arithmetization
MaRDI profile type: Publication
full work available at URL: s00224-009-9233-3
OpenAlex ID: W2091721024
cites work: On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
cites work: The division breakthroughs
cites work: Non-commutative arithmetic circuits: depth reduction and size lower bounds
cites work: Visibly pushdown languages
cites work: Automata, Languages and Programming
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Two Applications of Inductive Counting for Complementation Problems
cites work: An Optimal Parallel Algorithm for Formula Evaluation
cites work: Nondeterministic \(NC^1\) computation
cites work: Division in logspace-uniform NC
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Complexity theory of parallel time and hardware
cites work: Q4284250
cites work: Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
cites work: Q4385525
cites work: Arithmetizing Classes Around NC 1 and L
cites work: On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
cites work: Q3890112
cites work: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
cites work: \(\text{RL}\subseteq \text{SC}\)
cites work: Tree-size bounded alternation
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Properties that characterize LOGCFL
cites work: Q4393484
cites work: Q3341935
cites work: Boolean circuits versus arithmetic circuits
DOI: 10.1007/S00224-009-9233-3
description: scientific article; zbMATH DE number 5703835