scientific article; zbMATH DE number 1254648
From MaRDI portal
Publication:4227581
zbMath0918.68031MaRDI QIDQ4227581
Publication date: 24 February 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (only showing first 100 items - show all)
Systematic Refinement of Abstract State Machines with Higher-Order Logic ⋮ Expressiveness of Logic Programs under the General Stable Model Semantics ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ Reachability is in DynFO ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ THE MODAL LOGIC OF STEPWISE REMOVAL ⋮ First order quantifiers in monadic second order logic ⋮ Truth definitions in finite models ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures ⋮ CFI Construction and Balanced Graphs ⋮ Unnamed Item ⋮ FIRST-ORDER AXIOMATISATIONS OF REPRESENTABLE RELATION ALGEBRAS NEED FORMULAS OF UNBOUNDED QUANTIFIER DEPTH ⋮ Alternating (in)dependence-friendly logic ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Fixed points and attractors of reactantless and inhibitorless reaction systems ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Unnamed Item ⋮ Substitution Principle and semidirect products ⋮ Unnamed Item ⋮ Pure Pointer Programs with Iteration ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Fifty years of the spectrum problem: survey and new results ⋮ On the Computational Complexity of Non-Dictatorial Aggregation ⋮ Descriptive complexity of finite structures: Saving the quantifier rank ⋮ Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH ⋮ Monadic Second-Order Logic and Transitive Closure Logics over Trees ⋮ Circuit complexity of regular languages ⋮ Comparing the succinctness of monadic query languages over finite trees ⋮ Graph Grammars for Querying Graph-like Data ⋮ An empirical analysis of algorithms for partially Clairvoyant scheduling ⋮ Expressibility of Higher Order Logics ⋮ Positive predicate structures for continuous data ⋮ A local normal form theorem for infinitary logic with unary quantifiers ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ The Descriptive Complexity of the Deterministic Exponential Time Hierarchy ⋮ Unnamed Item ⋮ The descriptive complexity approach to LOGCFL ⋮ Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems ⋮ Unnamed Item ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ Independence-friendly logic without Henkin quantification ⋮ Weak models of distributed computing, with connections to modal logic ⋮ The complexity of properties of transformation semigroups ⋮ The ultra-weak Ash conjecture and some particular cases ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Unnamed Item ⋮ Equivalence Criteria for Compositional IF Modal Logics ⋮ Unnamed Item ⋮ Logic and Complexity in Cognitive Science ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm ⋮ Unnamed Item ⋮ Unnamed Item ⋮ First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Canonisation and Definability for Graphs of Bounded Rank Width ⋮ Complexity of model checking for reaction systems ⋮ Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Equivalence classes and conditional hardness in massively parallel computations ⋮ Approximate pattern matching and transitive closure logics. ⋮ Existential monadic second order logic on random rooted trees ⋮ Describing parameterized complexity classes ⋮ Computation by interaction for space-bounded functional programming ⋮ On symmetric circuits and fixed-point logics ⋮ Succinct definitions in the first order theory of graphs ⋮ Computing queries with higher-order logics ⋮ Closure properties of locally finite \(\omega\)-languages ⋮ Arithmetical definability and computational complexity ⋮ The equivalence of theories that characterize ALogTime ⋮ A logical approach to locality in pictures languages ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ Combining Model Checking and Deduction ⋮ The mu-calculus and Model Checking ⋮ A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ On FO 2 Quantifier Alternation over Words ⋮ On the expressive power of TeamLTL and first-order team logic over hyperproperties ⋮ Arity and alternation: a proper hierarchy in higher order logics ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Squeezing Feasibility ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ Program verification with interacting analysis plugins ⋮ Maintenance goals of agents in a dynamic environment: formulation and policy construction ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ Computational complexities of axiomatic extensions of monoidal t-norm based logic ⋮ The first order definability of graphs: Upper bounds for quantifier depth ⋮ Counter machines and distributed automata -- a story about exchanging space and time ⋮ Tight lower and upper bounds for the complexity of canonical colour refinement ⋮ An Ehrenfeucht-Fraïssé game approach to collapse results in database theory ⋮ Graph properties checkable in linear time in the number of vertices ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Emptiness problems for distributed automata ⋮ Computational Complexity Via Finite Types ⋮ Capturing MSO with One Quantifier ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ Contribution of Warsaw logicians to computational logic
This page was built for publication:
