<p>Found one clear link: work on <a href="https://pdf.sciencedirectassets.com/271596/1-s2.0-S0168007200X00632/1-s2.0-S0168007299000056/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEOH%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJHMEUCID5o55XwrqVRzgUAXAzgVMVWdPn2c21ZQdJuAmmsGa6fAiEAs1BUxjIo8zi926dsPsS0d%2BLoOryiSx5pKBDDzTz7OR0qswUIKRAFGgwwNTkwMDM1NDY4NjUiDAPITVg735q2FhcNXSqQBdi3BYmgFunHPc4dH9Jvujp1G3Hou0b2xr%2B8ts8qekbv00BaDH%2FiLNBFFLcMCWwPQXfOhya6W9eVK7IuOEQZFy71tVPR%2FmddW7fBPyDak5k3mveigwoeiGKEAob8xMR83r3aFzzVjdikkUKIkdsDlOc7bW6cAX235j6f2Y32gXTu%2B41Xm%2FdEZQef%2BzSlQpnhzxgpEjFZoPxFQ51mNKJyEe5kyeCJXMXoazXigVqHmeay4n0qIBNg%2BruL6jiOcuH3gaMQXPkSp9Fmu7mfiY9hJFMCIR3BlYzFwbglBZZK9RoCRI9zvhvymrtpIOc9Eqsupz8DdZKruh6a9HPeivrJBmjNSrK9CpTomFV2V4FvWC9MiPOvIvxTo94t1J2bpKmUQBq2KXT1x%2FDeMWRMQwljf8x4Z1HBlQLYRRnYMhFvn%2FBstIsRc2Shr38MWHt0ux%2BTX5uYOJmNurlE751WhWfPQOG%2FROSnCHYPWEA3j1yzM7PV7wPBpietZdi6hcqpOd4vE69%2BN64%2F6bY11zuoeY%2FPZe00Wu%2BWqlQsneR1xOXrCxSv6qgAuwKao%2BiCQawan0xXxtPFTQsTP9sUPjWc0N0CbrW6gR6CnelRr5UGbCYPID%2B0haKCGbSCK90x%2FR9lVWnp7qEDwiMN8BWrP0I86nHf2WjOzcbRBtOLV2r5%2FnsjsQ6k0AWz6BpvcM3VXu5AKuD4eEUmKwpQs64m7bl8Ms7bXseM%2Fx4i%2FpmJSO8IZa%2FeQHylORqLln4iwGcFymQQZIBz%2BoNg0FjfJ0Zqwm18WSI7PuvX0xfwPe%2BsIBqSauqevc3TCHQP4dzO4UaCWHDfkdnrB6SV4T2mRwP7u99D3N8UuVJieFW80hPMTDliLUQx3MTAMLyQwqoGOrEB2xp71NKgXVM5jo%2BA8ZuggudInr%2BxGdC8vGGUrI9FQCw9E6Z%2FlkRswsIyEtthw7QOO0PDvPI8M3xVm1ho1yNb5vuvoEPvtTtEb0D3tHh6Z8tOtsYL00FkqTusGcHbUoXaGej6tfcjfl27sLSh53sXdt2WdW82ILq99e6cEI9SVipxwUt4MSXuu1%2BYMb0oKtkRmRyUaD2LAFTciu7xp1v9G3A1sLzkP51WugHmD5ZKdano&amp;X-Amz-Algorithm=AWS4-HMAC-SHA256&amp;X-Amz-Date=20231112T090538Z&amp;X-Amz-SignedHeaders=host&amp;X-Amz-Expires=300&amp;X-Amz-Credential=ASIAQ3PHCVTY2B24N6SK%2F20231112%2Fus-east-1%2Fs3%2Faws4_request&amp;X-Amz-Signature=6b264350358c6c0c7c4ad5d6cdb945cf11793638ced6357ccca8ac2b44e2a46e&amp;hash=0461e5de7a7da16efccd7608cb267c3f1d2b87e97b441918b0412106e1ad27de&amp;host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&amp;pii=S0168007299000056&amp;tid=spdf-b13dcf24-d307-4175-80b2-5449d788e18f&amp;sid=bdc0ba5f7f50874c2f0859f-043b5c0d654egxrqb&amp;type=client&amp;tsoh=d3d3LnNjaWVuY2VkaXJlY3QuY29t&amp;ua=0e0b56565a005b025757&amp;rr=824d9d45fb7f2dc0&amp;cc=th" rel="nofollow noreferrer">Choiceless PTime characterization with ASM</a>. The introduction section explains that encoding to string is required for the Turing machines model, so ASM may be an alternative lifting need of such encoding.</p>
<p>At the same time seems like more recent articles about <a href="https://arxiv.org/pdf/2205.14003.pdf" rel="nofollow noreferrer">Choiceless PTime</a> do use/extend CPT logic from the first paper, but do not mention its relation to ASM.</p>

CC BY-SA 4.0
2023-11-12T09:10:02.910Z
2023-11-12T10:00:48.857Z
2023-11-12T10:00:48.857Z
uhbif19
<p>I learned about ASM recently and was interested how it could used for descriptive complexity theory.</p>
<p>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.</p>
<p>Is this possible to prove core description complexity theorems this way? Are there a reference for this? I did not found any.</p>

CC BY-SA 4.0
2023-11-08T08:41:36.677Z
SE did not sent last sentence. Fixed this. So hopefully closing cast for clarity is not standing anymore. If not, please articulate your position.
uhbif19
CC BY-SA 4.0
2023-11-09T08:19:49.723Z
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?
Bartosz Bednarczyk
CC BY-SA 4.0
2023-11-10T09:14:02.053Z
"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.
uhbif19
CC BY-SA 4.0
2023-11-10T09:17:41.173Z
> 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.
uhbif19
<cc.complexity-theory><descriptive-complexity><machine-models><finite-model-theory><first-order-logic>
Can one do descriptive complexity theory using abstract state machines?
uhbif19
# Can one do descriptive complexity theory using abstract state machines?

(Asked by: username_0 on 2023-11-08)

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.

**Tags:** cc.complexity-theory, descriptive-complexity, machine-models, finite-model-theory, first-order-logic

> **Comments:**
> **username_0**: SE did not sent last sentence. Fixed this. So hopefully closing cast for clarity is not standing anymore. If not, please articulate your position.  
> **username_1**: 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?  
> **username_0**: "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.  
> **username_0**: > 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.  

---

## 1 answers

### Answer by username_0 on 2023-11-12. Score: 0

Found one clear link: work on [Choiceless PTime characterization with ASM](https://pdf.sciencedirectassets.com/271596/1-s2.0-S0168007200X00632/1-s2.0-S0168007299000056/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEOH%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJHMEUCID5o55XwrqVRzgUAXAzgVMVWdPn2c21ZQdJuAmmsGa6fAiEAs1BUxjIo8zi926dsPsS0d%2BLoOryiSx5pKBDDzTz7OR0qswUIKRAFGgwwNTkwMDM1NDY4NjUiDAPITVg735q2FhcNXSqQBdi3BYmgFunHPc4dH9Jvujp1G3Hou0b2xr%2B8ts8qekbv00BaDH%2FiLNBFFLcMCWwPQXfOhya6W9eVK7IuOEQZFy71tVPR%2FmddW7fBPyDak5k3mveigwoeiGKEAob8xMR83r3aFzzVjdikkUKIkdsDlOc7bW6cAX235j6f2Y32gXTu%2B41Xm%2FdEZQef%2BzSlQpnhzxgpEjFZoPxFQ51mNKJyEe5kyeCJXMXoazXigVqHmeay4n0qIBNg%2BruL6jiOcuH3gaMQXPkSp9Fmu7mfiY9hJFMCIR3BlYzFwbglBZZK9RoCRI9zvhvymrtpIOc9Eqsupz8DdZKruh6a9HPeivrJBmjNSrK9CpTomFV2V4FvWC9MiPOvIvxTo94t1J2bpKmUQBq2KXT1x%2FDeMWRMQwljf8x4Z1HBlQLYRRnYMhFvn%2FBstIsRc2Shr38MWHt0ux%2BTX5uYOJmNurlE751WhWfPQOG%2FROSnCHYPWEA3j1yzM7PV7wPBpietZdi6hcqpOd4vE69%2BN64%2F6bY11zuoeY%2FPZe00Wu%2BWqlQsneR1xOXrCxSv6qgAuwKao%2BiCQawan0xXxtPFTQsTP9sUPjWc0N0CbrW6gR6CnelRr5UGbCYPID%2B0haKCGbSCK90x%2FR9lVWnp7qEDwiMN8BWrP0I86nHf2WjOzcbRBtOLV2r5%2FnsjsQ6k0AWz6BpvcM3VXu5AKuD4eEUmKwpQs64m7bl8Ms7bXseM%2Fx4i%2FpmJSO8IZa%2FeQHylORqLln4iwGcFymQQZIBz%2BoNg0FjfJ0Zqwm18WSI7PuvX0xfwPe%2BsIBqSauqevc3TCHQP4dzO4UaCWHDfkdnrB6SV4T2mRwP7u99D3N8UuVJieFW80hPMTDliLUQx3MTAMLyQwqoGOrEB2xp71NKgXVM5jo%2BA8ZuggudInr%2BxGdC8vGGUrI9FQCw9E6Z%2FlkRswsIyEtthw7QOO0PDvPI8M3xVm1ho1yNb5vuvoEPvtTtEb0D3tHh6Z8tOtsYL00FkqTusGcHbUoXaGej6tfcjfl27sLSh53sXdt2WdW82ILq99e6cEI9SVipxwUt4MSXuu1%2BYMb0oKtkRmRyUaD2LAFTciu7xp1v9G3A1sLzkP51WugHmD5ZKdano&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20231112T090538Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTY2B24N6SK%2F20231112%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=6b264350358c6c0c7c4ad5d6cdb945cf11793638ced6357ccca8ac2b44e2a46e&hash=0461e5de7a7da16efccd7608cb267c3f1d2b87e97b441918b0412106e1ad27de&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S0168007299000056&tid=spdf-b13dcf24-d307-4175-80b2-5449d788e18f&sid=bdc0ba5f7f50874c2f0859f-043b5c0d654egxrqb&type=client&tsoh=d3d3LnNjaWVuY2VkaXJlY3QuY29t&ua=0e0b56565a005b025757&rr=824d9d45fb7f2dc0&cc=th). The introduction section explains that encoding to string is required for the Turing machines model, so ASM may be an alternative lifting need of such encoding.

At the same time seems like more recent articles about [Choiceless PTime](https://arxiv.org/pdf/2205.14003.pdf) do use/extend CPT logic from the first paper, but do not mention its relation to ASM.


---

