Regular Graphs and the Spectra of Two-Variable Logic with Counting
From MaRDI portal
Publication:5258916
DOI10.1137/130943625zbMath1354.03039arXiv1304.0829OpenAlexW2964224456MaRDI QIDQ5258916
Publication date: 24 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.0829
regular graphssemilinear setsPresburger arithmeticfirst-order spectratwo-variable logic with counting
Model theory of finite structures (03C13) Vertex degrees (05C07) Subsystems of classical logic (including intuitionistic logic) (03B20) Basic properties of first-order languages and structures (03C07)
Related Items (3)
A logical approach to locality in pictures languages ⋮ Graphs Identified by Logics with Counting ⋮ Unnamed Item
Cites Work
- First-order spectra with one variable
- On logics with two variables
- Semigroups, Presburger formulas, and languages
- Complexity of the two-variable fragment with counting quantifiers
- The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
- Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
- The Spectra of First-Order Sentences and Computational Complexity
- The two‐variable fragment with counting and equivalence
- An Algorithm for the General Petri Net Reachability Problem
- Universal quantifiers and time complexity of random access machines
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Complexity classes and theories of finite models
- On languages with two variables
- Rudimentary Predicates and Relative Computation
- On the Decision Problem for Two-Variable First-Order Logic
- Turing machines and the spectra of first-order formulas
- Fifty years of the spectrum problem: survey and new results
- Complexity Results for First-Order Two-Variable Logic with Counting
- On spectra of sentences of monadic second order logic with counting
- Bemerkungen zum Spektralproblem
- Two-Variable First-Order Logic with Equivalence Closure
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Regular Graphs and the Spectra of Two-Variable Logic with Counting
