Generalising automaticity to modal properties of finite structures

DOI10.1016/J.TCS.2007.03.048MaRDI QIDQ2373714zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anuj Dawar, Stephan Kreutzer

Publication date 16 July 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.03.048

zbMATH Keywords

automatacomplexityfixed-point logicsmodal logics

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 1954377
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• Theories of Automatic Structures and Their Complexity
• Model-theoretic complexity of automatic structures
• The expressive power of fixed-point logic with counting

Cites work

• A restricted second order logic for finite structures
• An automata-theoretic approach to branching-time model checking
• Automaticity. I: Properties of a measure of descriptional complexity
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• scientific article; zbMATH DE number 176754 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1954377 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Inflationary fixed points in modal logic
• Modal logic
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
• Rudiments of \(\mu\)-calculus

Cited in

(1)

• scientific article; zbMATH DE number 1954377 (Why is no real title available?)

This page was built for publication: Generalising automaticity to modal properties of finite structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373714)