Languages defined with modular counting quantifiers

DOI10.1006/inco.2000.2923zbMath1007.68071OpenAlexW2078875286MaRDI QIDQ1854424

Howard Straubing

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2000.2923

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (3)

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture ⋮ Unnamed Item ⋮ Difference hierarchies and duality with an application to formal languages

Cites Work

• Non-uniform automata over groups
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Bounded-depth, polynomial-size circuits for symmetric functions
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Classification of finite monoids: the language approach
• Regular languages in \(NC\)
• Finite semigroup varieties defined by programs
• Regular languages defined with generalized quantifiers
• Superlinear lower bounds for bounded-width branching programs
• On the computational power of depth 2 circuits with threshold and modulo gates
• Weak Second‐Order Arithmetic and Finite Automata
• Parity, circuits, and the polynomial-time hierarchy
• A logic for constant-depth circuits
• Languages that Capture Complexity Classes
• Finite monoids and the fine structure of NC ¹
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Languages defined with modular counting quantifiers