Monadic generalized spectra

From MaRDI portal
Publication:4078009

DOI10.1002/malq.19750210112zbMath0317.02054OpenAlexW2003895694MaRDI QIDQ4078009

Ronald Fagin

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 LOGICOne unary function says less than two in existential second order logicA logical approach to locality in pictures languagesExistential MSO over two successors is strictly weaker than over linear ordersGeneralized quantifiers and pebble games on finite structuresFirst-order spectra with one binary predicateProbabilities of First-Order Sentences about Unary FunctionsUnnamed ItemFirst order quantifiers in monadic second order logicOn spectra of sentences of monadic second order logic with countingCan datalog be approximated?Hierarchies in transitive closure logic, stratified Datalog and infinitary logicOn winning Ehrenfeucht games and monadic NPA Conjecture Concerning the Spectrum of a SentenceThe dimension of the negation of transitive closureReachability is harder for directed than for undirected finite graphsA probabilistic view of Datalog parallelizationThe complexity of graph connectivityComparing the power of monadic NP gamesNonstandard methods for finite structuresTree-width and the monadic quantifier hierarchy.Hybrid planning for challenging construction problems: an answer set programming approachRegular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order LogicFirst-order spectra with one variableDatalog extensions for database queries and updatesComputing on structuresComparing the Power of Games on GraphsMonadic partition logics and finite automataFifty years of the spectrum problem: survey and new resultsA note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)Graph Connectivity, Monadic NP and built-in relations of moderate degreeThe functional dimension of inductive definitionsInfinitary logics and 0-1 lawsThe quantifier structure of sentences that characterize nondeterministic time complexityFinite-model theory -- A personal perspectiveMonadic Second-Order Logic and Transitive Closure Logics over TreesComparing the succinctness of monadic query languages over finite treesThe fine spectrum of a varietyThe monadic quantifier alternation hierarchy over grids and graphsInfinitary logic for computer scienceBounds in the propagation of selection into logic programsOn winning strategies in Ehrenfeucht-Fraïssé gamesPartially ordered connectives and monadic monotone strict NPArity bounds in first-order incremental evaluation and definition of polynomial time database queriesThe closure of monadic NPOn sets of relations definable by additionStructure and complexity of relational queriesOn the definability of properties of finite graphsAlmost Everywhere Equivalence of Logics in Finite Model TheoryComplexity classes and theories of finite models




This page was built for publication: Monadic generalized spectra