Languages defined with modular counting quantifiers

DOI10.1006/INCO.2000.2923MaRDI QIDQ1854424zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 1136081
• Definability of Languages by Generalized First-Order Formulas over (N,+)
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Regular languages defined with generalized quantifiers
• Circuit complexity and the expressive power of generalized first-order formulas

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A logic for constant-depth circuits
• 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
• Finite monoids and the fine structure of NC ¹
• Finite semigroup varieties defined by programs
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Languages that Capture Complexity Classes
• Non-uniform automata over groups
• On the computational power of depth 2 circuits with threshold and modulo gates
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages defined with generalized quantifiers
• Regular languages in \(NC\)
• Superlinear lower bounds for bounded-width branching programs
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(14)

• On languages in countably generated semilattices
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Counting modulo quantifiers on finite structures
• Difference hierarchies and duality with an application to formal languages
• A note on some languages in uniform \(ACC^ 0\)
• Modular quantifiers
• Indexed counter languages
• Sur le produit avec compteur modulo un nombre premier
• scientific article; zbMATH DE number 1136081 (Why is no real title available?)
• Tameness and the power of programs over monoids in \(\mathbf{DA}\)
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Definability of Languages by Generalized First-Order Formulas over (N,+)
• Quantitative Languages Defined by Functional Automata
• The regular languages of first-order logic with one alternation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854424)