Extensions to Barrington's M-program model

DOI10.1016/0304-3975(93)90253-PzbMath0764.68040OpenAlexW2077543142MaRDI QIDQ1208406

François Bédard, Pierre McKenzie, François Lemieux

Publication date: 16 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90253-p

zbMATH Keywords

growing abelian monoid sequencespolynomial-length programspolynomially growing groupoid sequences

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Finite loops recognize exactly the regular open languages ⋮ Generalized quantifier and a bounded arithmetic theory for LOGCFL ⋮ McNaughton families of languages. ⋮ On Second-Order Monadic Groupoidal Quantifiers ⋮ Space Complexity of Reachability Testing in Labelled Graphs ⋮ The descriptive complexity approach to LOGCFL ⋮ Cost Register Automata for Nested Words ⋮ Languages recognized by finite aperiodic groupoids ⋮ Nondeterministic \(NC^1\) computation ⋮ Circuits and expressions with nonassociative gates ⋮ Space complexity of reachability testing in labelled graphs ⋮ Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(NC^ 1\): The automata-theoretic viewpoint
• Turing machines that take advice
• Non-uniform automata over groups
• Parallel computation with threshold functions
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Tree-size bounded alternation
• On uniform circuit complexity
• Properties that characterize LOGCFL
• General context-free recognition in less than cubic time
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• A taxonomy of problems with fast parallel algorithms
• Problems complete for deterministic logarithmic space
• Finite monoids and the fine structure of NC ¹
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• On the Tape Complexity of Deterministic Context-Free Languages
• Relations Among Complexity Measures
• The Hardest Context-Free Language

This page was built for publication: Extensions to Barrington's M-program model