Definability of Languages by Generalized First-Order Formulas over (N,+)

DOI10.1007/11672142_40MaRDI QIDQ5449824zbMATH OpenOpenAlexFDO

Authors Amitabha Roy, Howard Straubing

Publication date 19 March 2008

Published in STACS 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11672142_40

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Automata and formal grammars in connection with logical questions (03D05) Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Languages defined with modular counting quantifiers
• scientific article; zbMATH DE number 1136081
• Non-definability of Languages by Generalized First-order Formulas over (N,+)
• Regular languages defined with generalized quantifiers

Cited in

(15)

• Regular languages defined by generalized first-order formulas with a bounded number of bound variables
• Counting modulo quantifiers on finite structures
• Languages defined with modular counting quantifiers
• On languages defined by generalized principal right congruences
• First order extensions of residue classes and uniform circuit complexity
• Non-definability of Languages by Generalized First-order Formulas over (N,+)
• scientific article; zbMATH DE number 4204325 (Why is no real title available?)
• scientific article; zbMATH DE number 1261672 (Why is no real title available?)
• scientific article; zbMATH DE number 1101593 (Why is no real title available?)
• scientific article; zbMATH DE number 1136081 (Why is no real title available?)
• Arithmetical definability over finite structures
• On Existentially First-Order Definable Languages and Their Relation to NP
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Methods of class field theory to separate logics over finite residue classes and circuit complexity
• An Ehrenfeucht-Fraïssé game approach to collapse results in database theory

This page was built for publication: Definability of Languages by Generalized First-Order Formulas over (N,+)

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