# Can one do descriptive complexity theory using abstract state machines?

I learned about ASM recently and was interested how it could used for descriptive complexity theory.

Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. Refining ASM further you get regular machine and prove complexity bound for it.

Is this possible to prove core description complexity theorems this way? Are there a reference for this? I did not found any.

• SE did not sent last sentence. Fixed this. So hopefully closing cast for clarity is not standing anymore. If not, please articulate your position. Nov 8 at 8:41
• Your question is not clear, for instance what do you mean by an "algebraic model of a formula"? What is more, your first sentence speaks about "descriptive complexity" while the last one refers to "description complexity". These are two different things. Which you do you have in mind? Nov 9 at 8:19
• "Which you do you have in mind?" I mean the link between FMT and complexity theory. The one which is in Fagin theorem or Neil Immerman "Descriptive Complexity" book. Nov 10 at 9:14
• > what do you mean by an "algebraic model of a formula" Well, that is kinda the point of this question, how would you construct such an "algebraic model" and if it is possible at all. If I know exactly how to do it, then why would I need to ask? As I see it you might have "empty" structure as the first step of ASM and add "fresh" variables trying to conform to the formula at each step. That seems like an algoritmisation of constructing some syntactic "free" model to me. Nov 10 at 9:17