Program schemes, arrays, Lindström quantifiers and zero-one laws
DOI10.1016/S0304-3975(01)00183-9zbMATH Open1018.03023OpenAlexW1997448383MaRDI QIDQ1606129FDOQ1606129
Authors: Iain Stewart 
Publication date: 31 July 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00183-9
Recommendations
- Publication:4945239
- scientific article; zbMATH DE number 1796951
- Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws
- On strictly arithmetical completeness in logics of programs
- Halting and equivalence of program schemes in models of arbitrary theories
- Zero-one laws for first-order formulas with a bounded quantifier depth
- scientific article; zbMATH DE number 3864500
- scientific article; zbMATH DE number 1272994
- scientific article; zbMATH DE number 732053
- scientific article; zbMATH DE number 139629
Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)
Cites Work
- Title not available (Why is that?)
- Probabilities on finite models
- Logical and schematic characterization of complexity classes
- Datalog extensions for database queries and updates
- Title not available (Why is that?)
- An observation on time-storage trade off
- Context-sensitive transitive closure operators
- Languages that Capture Complexity Classes
- Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
- Title not available (Why is that?)
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Even Simple Programs Are Hard To Analyze
- Title not available (Why is that?)
- Complexity of some problems in Petri nets
- Generalized Quantifiers and Logical Reducibilities
- Title not available (Why is that?)
- Persistence of vector replacement systems is decidable
- Title not available (Why is that?)
- Structure and complexity of relational queries
- Logical Description of Monotone NP Problems
- Title not available (Why is that?)
- Infinitary logics and 0-1 laws
- Using the Hamiltonian path operator to capture NP
- Title not available (Why is that?)
- Title not available (Why is that?)
- The expressive power of stratified logic programs
- Complete Problems Involving Boolean Labelled Structures and Projection Transactions
- On Classes of Program Schemata
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Arity hierarchies
- Relativized logspace and generalized quantifiers over finite ordered structures
- Some relationships between logics of programs and complexity theory
- On static logics, dynamic logics, and complexity classes
- Hierarchies in classes of program schemes
- On the power of built-in relations in certain classes of program schemes
- Adding for-loops to first-order logic
- Existential least fixed-point logic and its relatives
Cited In (10)
- An infinite hierarchy in a class of polynomial-time program schemes
- Logical and Complexity-theoretic Aspects of Models of Computation with Restricted Access to Arrays
- Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures
- Hierarchies in classes of program schemes
- Program Schemes with Deep Pushdown Storage
- Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws
- On the power of deep pushdown stacks
- Title not available (Why is that?)
- Programs over semigroups of dot-depth one
- Title not available (Why is that?)
This page was built for publication: Program schemes, arrays, Lindström quantifiers and zero-one laws
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1606129)
