Monadic generalized spectra
From MaRDI portal
Publication:4078009
DOI10.1002/malq.19750210112zbMath0317.02054OpenAlexW2003895694MaRDI QIDQ4078009
Publication date: 1975
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19750210112
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (50)
GAMES AND CARDINALITIES IN INQUISITIVE FIRST-ORDER LOGIC ⋮ One unary function says less than two in existential second order logic ⋮ A logical approach to locality in pictures languages ⋮ Existential MSO over two successors is strictly weaker than over linear orders ⋮ Generalized quantifiers and pebble games on finite structures ⋮ First-order spectra with one binary predicate ⋮ Probabilities of First-Order Sentences about Unary Functions ⋮ Unnamed Item ⋮ First order quantifiers in monadic second order logic ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Can datalog be approximated? ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ On winning Ehrenfeucht games and monadic NP ⋮ A Conjecture Concerning the Spectrum of a Sentence ⋮ The dimension of the negation of transitive closure ⋮ Reachability is harder for directed than for undirected finite graphs ⋮ A probabilistic view of Datalog parallelization ⋮ The complexity of graph connectivity ⋮ Comparing the power of monadic NP games ⋮ Nonstandard methods for finite structures ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Hybrid planning for challenging construction problems: an answer set programming approach ⋮ Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic ⋮ First-order spectra with one variable ⋮ Datalog extensions for database queries and updates ⋮ Computing on structures ⋮ Comparing the Power of Games on Graphs ⋮ Monadic partition logics and finite automata ⋮ Fifty years of the spectrum problem: survey and new results ⋮ A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\) ⋮ Graph Connectivity, Monadic NP and built-in relations of moderate degree ⋮ The functional dimension of inductive definitions ⋮ Infinitary logics and 0-1 laws ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Finite-model theory -- A personal perspective ⋮ Monadic Second-Order Logic and Transitive Closure Logics over Trees ⋮ Comparing the succinctness of monadic query languages over finite trees ⋮ The fine spectrum of a variety ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Infinitary logic for computer science ⋮ Bounds in the propagation of selection into logic programs ⋮ On winning strategies in Ehrenfeucht-Fraïssé games ⋮ Partially ordered connectives and monadic monotone strict NP ⋮ Arity bounds in first-order incremental evaluation and definition of polynomial time database queries ⋮ The closure of monadic NP ⋮ On sets of relations definable by addition ⋮ Structure and complexity of relational queries ⋮ On the definability of properties of finite graphs ⋮ Almost Everywhere Equivalence of Logics in Finite Model Theory ⋮ Complexity classes and theories of finite models
This page was built for publication: Monadic generalized spectra