Automatic structures: twenty years later

DOI10.1145/3373718.3394734MaRDI QIDQ5145615zbMATH OpenOpenAlexFDO

Authors Erich Grädel

Publication date 21 January 2021

Published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3373718.3394734

zbMATH Keywords

automatic structuresdecidable theoriesfinitely presentable structuresinterpretations

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05) Theory of numerations, effectively presented structures (03D45) Formal languages and automata (68Q45)

Recommendations

• Theories of Automatic Structures and Their Complexity
• scientific article; zbMATH DE number 2040323
• Automatic Structures: Richness and Limitations
• Automatic Structures of Bounded Degree Revisited
• Automatic structures of bounded degree

Cited in

(20)

• Symbolic automatic relations and their applications to SMT and CHC solving
• Second-order finite automata
• Lamplighter groups and automata
• Automatic structures
• A computation model with automatic functions and relations as primitive operations
• String compression in FA-presentable structures
• Three lectures on automatic structures
• scientific article; zbMATH DE number 2040323 (Why is no real title available?)
• Addition machines, automatic functions and open problems of Floyd and Knuth
• Ramsey quantifiers over automatic structures: complexity and applications to verification
• Quasi-isometric reductions between infinite strings
• The theory of reachability of trace-pushdown systems
• A class of rational trace relations closed under composition
• Computable classifications of continuous, transducer, and regular functions
• Existential definability of unary predicates in Büchi arithmetic
• Paths, ends and the separation problem for infinite graphs
• An introduction to the theory of linear integer arithmetic (invited paper)
• Games with -automatic preference relations
• Word structures and their automatic presentations
• Karp's NP-complete problems over first-order definable structures

This page was built for publication: Automatic structures: twenty years later

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