ComputingComputer ScienceAutomationLogicSet TheoryAutomata TheoryAutomated ReasoningComputational ModelsFinite AutomataDecision ProceduresFinite Automata Theory
We study definability and complexity issues for automatic and /spl omega/-automatic structures. These are, in general, infinite structures but they can be finitely presented by a collection of automata. Moreover they admit effective (in fact automatic) evaluation of all first-order queries. Therefore, automatic structures provide an interesting framework for extending many algorithmic and logical methods from finite structures to infinite ones. We explain the notion of (/spl omega/-)automatic structures, give examples, and discuss the relationship to automatic groups. We determine the complexity of model checking and query evaluation on automatic structures for fragments of first-order logic. Further we study closure properties and definability issues on automatic structures and present a technique for proving that a structure is not automatic. We give model-theoretic characterisations for automatic structures via interpretations. Finally we discuss the composition theory of automatic structures and prove that they are closed under finitary Feferman-Vaught-like products.
8
Choice Reviews Online · 1995 · 1.8K citations
Word problems requiring exponential time(Preliminary Report)
Larry J. Stockmeyer, Albert R. Meyer · 1973 · 874 citations
The Boolean formula value problem is in ALOGTIME
Sam Buss · 1987 · 241 citations