Some new results in monadic second-order arithmetic
From MaRDI portal
Publication:3195649
DOI10.3233/COM-150036zbMath1337.03087MaRDI QIDQ3195649
Publication date: 20 October 2015
Published in: Computability (Search for Journal in Brave)
03D15: Complexity of computation (including implicit computational complexity)
03F35: Second- and higher-order arithmetic and fragments
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- A note on definability in fragments of arithmetic with free unary predicates
- On Pascal triangles modulo a prime power
- Definability, decidability, complexity
- Presburger arithmetic with unary predicates is Π11 complete
- Undecidable extensions of Skolem arithmetic
- The theory of integer multiplication with order restricted to primes is decidable
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Definability and decision problems in arithmetic
- A list of arithmetical structures complete with respect to the first-order definability