Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$

DOI10.1137/060658035zbMath1135.03013OpenAlexW2008235772MaRDI QIDQ5386211

Howard Straubing, Amitabha Roy

Publication date: 22 April 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/47e4e332ba1cc38d76aa052bb7d9d6192e40f14d

zbMATH Keywords

semigroup theorycircuit complexityfinite model theory

Mathematics Subject Classification ID

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

Related Items (2)

First-order logics: some characterizations and closure properties ⋮ Unnamed Item

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