Logically defined subsets of \(\mathbb{N}{}^ k\)

DOI10.1016/0304-3975(92)90328-DzbMath0747.03017MaRDI QIDQ1186601

Pierre Péladeau

Publication date: 28 June 1992

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

zbMATH Keywords

rational subsetsrational languagerecognizable subsetsparallel complexity class ACC\(^ 0\)semi-simple sets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (8)

On the open problem of Ginsburg concerning semilinear sets and related problems ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ Existential Definability over the Subword Ordering ⋮ Deciding whether a relation defined in Presburger logic can be defined in weaker logics ⋮ Formulas, regular languages and Boolean circuits ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ Local testability from words to traces, a suitable definition ⋮ Model Checking FO(R) over One-Counter Processes and beyond

Cites Work

• Semigroups, Presburger formulas, and languages
• Rational sets in commutative monoids
• Weak Second‐Order Arithmetic and Finite Automata
• A logic for constant-depth circuits
• Languages that Capture Complexity Classes
• Finite monoids and the fine structure of NC ¹
• Application of model theoretic games to discrete linear orders and finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Logically defined subsets of \(\mathbb{N}{}^ k\)