An optimal construction of Hanf sentences
From MaRDI portal
Publication:420856
DOI10.1016/j.jal.2012.01.002zbMath1258.03048arXiv1105.5487OpenAlexW2963528658MaRDI QIDQ420856
Benedikt Bollig, Dietrich Kuske
Publication date: 23 May 2012
Published in: Journal of Applied Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1105.5487
Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13)
Related Items
The complexity of model checking multi-stack systems ⋮ Unnamed Item ⋮ An Automaton over Data Words That Captures EMSO Logic ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Elements of finite model theory.
- Muller message-passing automata and logics
- Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Decidable first-order theories of one-step rewriting in trace monoids
- The complexity of first-order and monadic second-order logic revisited
- On monadic NP vs monadic co-NP
- Monadic second-order logic over rectangular pictures and recognizability by tiling systems
- Message-passing automata are expressively equivalent to EMSO logic
- Automatic structures of bounded degree revisited
- Deciding first-order properties of locally tree-decomposable structures
- A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES
- Hereditary undecidability of some theories of finite structures
- First-order queries on structures of bounded degree are computable with constant delay
- First-order and counting theories ofω-automatic structures
- Model Theory Makes Formulas Large
- Logics with counting and local properties
- On the extending of models (I)
