Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912895263047680 |
|---|---|
| author | Ham, Lucy Jackson, Marcel |
| author_facet | Ham, Lucy Jackson, Marcel |
| contents | We explore new interactions between finite model theory and classical streams of universal algebra and semigroup theory. A key result is an example of finite algebras whose variety is not finitely axiomatisable in first order logic, but where the class of finite members are finitely axiomatisable amongst finite algebras. These algebras present a negative solution to a first order formulation of the Eilenberg-Schützenberger problem, and witness the simultaneous failure of the Łos-Tarski Theorem, the SP-Preservation Theorem and Birkhoff's HSP-Preservation Theorem at the finite level. The examples also show that a pseudovariety without any finite pseudoequational basis may be finitely axiomatisable in first order logic amongst finite algebras. Other results include the undecidability of deciding first order definability of the pseudovariety of a finite algebra, and a mapping from any fixed finite template constraint satisfaction problem to a first order equivalent variety membership problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_02653 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexity Ham, Lucy Jackson, Marcel Logic Computational Complexity Logic in Computer Science 03C13, 08B05, 08B26, 68Q15, 68Q19, 08A30, 20M07 We explore new interactions between finite model theory and classical streams of universal algebra and semigroup theory. A key result is an example of finite algebras whose variety is not finitely axiomatisable in first order logic, but where the class of finite members are finitely axiomatisable amongst finite algebras. These algebras present a negative solution to a first order formulation of the Eilenberg-Schützenberger problem, and witness the simultaneous failure of the Łos-Tarski Theorem, the SP-Preservation Theorem and Birkhoff's HSP-Preservation Theorem at the finite level. The examples also show that a pseudovariety without any finite pseudoequational basis may be finitely axiomatisable in first order logic amongst finite algebras. Other results include the undecidability of deciding first order definability of the pseudovariety of a finite algebra, and a mapping from any fixed finite template constraint satisfaction problem to a first order equivalent variety membership problem. |
| title | Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexity |
| topic | Logic Computational Complexity Logic in Computer Science 03C13, 08B05, 08B26, 68Q15, 68Q19, 08A30, 20M07 |
| url | https://arxiv.org/abs/2212.02653 |