An extension of fixpoint logic with a symmetry-based choice construct

DOI10.1006/inco.1998.2712zbMath0915.68043OpenAlexW1966941526MaRDI QIDQ1271477

H. K. Hoang, F. Gire

Publication date: 22 June 1999

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1998.2712

zbMATH Keywords

restricted non-determinismsymmetry-based choice operator

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45)

Related Items (5)

On the Descriptive Complexity of Linear Algebra ⋮ Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Computation on structures. Behavioural theory, logic, complexity ⋮ On polynomial time computation over unordered structures

Cites Work

• Unnamed Item
• Computable queries for relational data bases
• Upper and lower bounds for first order expressibility
• Non-determinism in logic-based languages
• Structure and complexity of relational queries
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Expressiveness of efficient semi-deterministic choice constructs

This page was built for publication: An extension of fixpoint logic with a symmetry-based choice construct