Automata Presenting Structures: A Survey of the Finite String Case
The Bulletin of Symbolic Logic 14 (2):169 - 209 (2008)
| Abstract | A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,631 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesMarcin Mostowski (1998). Computational Semantics for Monadic Quantifiers. Journal of Applied Non--Classical Logics 8:107--121.
Mirosław Kutyłowski (1988). Finite Automata, Real Time Processes and Counting Problems in Bounded Arithmetics. Journal of Symbolic Logic 53 (1):243-258.
Brenda J. Latka (1994). Finitely Constrained Classes of Homogeneous Directed Graphs. Journal of Symbolic Logic 59 (1):124-139.
Till Tantau (2005). Weak Cardinality Theorems. Journal of Symbolic Logic 70 (3):861 - 878.
Raymond J. Nelson (1975). Behaviorism, Finite Automata, and Stimulus-Response Theory. Theory and Decision 6 (August):249-67.
Yuri Gurevich & Saharon Shelah (1996). On Finite Rigid Structures. Journal of Symbolic Logic 61 (2):549-562.
Ian Hodkinson & Martin Otto (2003). Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures. Bulletin of Symbolic Logic 9 (3):387-405.
H. D. MacPherson, M. Pouzet & R. E. Woodrow (1992). Countable Structures of Given Age. Journal of Symbolic Logic 57 (3):992-1010.
Jakub Szymanik & Marcin Zajenkowski (2009). Understanding Quantifiers in Language. In N. A. Taatgen & H. van Rijn (eds.), Proceedings of the 31st Annual Conference of the Cognitive Science Society.
I. M. Hodkinson & H. D. Macpherson (1988). Relational Structures Determined by Their Finite Induced Substructures. Journal of Symbolic Logic 53 (1):222-230.
Gunther Mainhardt (2004). P Versus Np and Computability Theoretic Constructions in Complexity Theory Over Algebraic Structures. Journal of Symbolic Logic 69 (1):39-64.
J.-P. Moulin (1992). Modifiable Automata Self-Modifying Automata. Acta Biotheoretica 40 (2-3).
Ross Willard (1994). Hereditary Undecidability of Some Theories of Finite Structures. Journal of Symbolic Logic 59 (4):1254-1262.
Analytics
Monthly downloads |
Added to index2010-08-30Total downloads2 ( #232,211 of 548,969 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
