Geodesic
On complexity of problem of satisfiability for systems of countable-valued functional equations
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2015), pp. 25-32.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the problem of satisfiability for systems of countable-valued functional equations, containing ternary discriminator function $p$. We prove that this problem is $m$-complete in the class $\Pi_1$ of Kleene–Mostovsky's hierarchy.
Keywords: functional equations, countable-valued logic, problem of satisfiability. 
@article{IVM_2015_8_a2,
     author = {I. S. Kalinina and S. S. Marchenkov},
     title = {On complexity of problem of satisfiability for systems of countable-valued functional equations},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {25--32},
     publisher = {mathdoc},
     number = {8},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2015_8_a2/}
}
TY  - JOUR
AU  - I. S. Kalinina
AU  - S. S. Marchenkov
TI  - On complexity of problem of satisfiability for systems of countable-valued functional equations
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2015
SP  - 25
EP  - 32
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2015_8_a2/
LA  - ru
ID  - IVM_2015_8_a2
ER  - 
%0 Journal Article
%A I. S. Kalinina
%A S. S. Marchenkov
%T On complexity of problem of satisfiability for systems of countable-valued functional equations
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2015
%P 25-32
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2015_8_a2/
%G ru
%F IVM_2015_8_a2
I. S. Kalinina; S. S. Marchenkov. On complexity of problem of satisfiability for systems of countable-valued functional equations. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2015), pp. 25-32. http://geodesic.mathdoc.fr/item/IVM_2015_8_a2/

[1] Ekin O., Foldes S., Hammer P. L., Hellerstein L., “Equational characterizations of Boolean function classes”, Discrete Math., 211 (2000), 27–51 | DOI | MR | Zbl

[2] Foldes S., “Equational classes of Boolean functions via the HSP theorem”, Algebra Univers., 44 (2000), 309–324 | DOI | MR | Zbl

[3] Pippenger N., “Galois theory for minors of finite functions”, Discrete Math., 254 (2002), 405–419 | DOI | MR | Zbl

[4] Marchenkov S. S., “Operator zamykaniya v mnogoznachnoi logike, baziruyuschiisya na funktsionalnykh uravneniyakh”, Diskret. analiz i issled. operatsii, 17:4 (2010), 18–31 | MR | Zbl

[5] Marchenkov S. S., “O klassifikatsiyakh funktsii mnogoznachnoi logiki s pomoschyu grupp avtomorfizmov”, Diskret. analiz i issled. operatsii, 18:4 (2011), 66–76 | MR | Zbl

[6] Marchenkov S. S., “FE-klassifikatsiya funktsii mnogoznachnoi logiki”, Vest. MGU. Ser. 15. Vychisl. matem. i kibernetika, 2011, no. 2, 32–39 | MR

[7] Marchenkov S. S., Fedorova V. S., “O resheniyakh sistem funktsionalnykh bulevykh uravnenii”, Diskret. analiz i issled. operatsii, 15:6 (2008), 48–57 | MR | Zbl

[8] Marchenkov S. S., Fedorova V. S., “O resheniyakh sistem funktsionalnykh uravnenii mnogoznachnoi logiki”, Dokl. RAN, 426:4 (2009), 448–449 | MR | Zbl

[9] Marchenkov S. S., Fedorova V. S., “Resheniya sistem funktsionalnykh uravnenii mnogoznachnoi logiki”, Vest. MGU. Ser. 15. Vychisl. matem. i kibernetika, 2009, no. 4, 29–33 | MR | Zbl

[10] Fedorova V. S., “O slozhnosti problemy vypolnimosti sistemy funktsionalnykh bulevykh uravnenii”, Diskret. analiz i issled. operatsii, 20:3 (2013), 84–100 | MR

[11] Marchenkov S. S., “Opredelimost v yazyke funktsionalnykh uravnenii schetnoznachnoi logiki”, Diskret. matem., 25:4 (2013), 13–23 | DOI | MR | Zbl

[12] Marchenkov S. S., Kalinina I. S., “Operator FE-zamykaniya v schetnoznachnoi logike”, Vest. MGU. Ser. 15. Vychisl. matem. i kibernetika, 2013, no. 3, 42–47 | MR

[13] Marchenkov S. S., “Odnorodnye algebry”, Probl. kibernetiki, 39, 1982, 85–106 | MR | Zbl

[14] Marchenkov S. S., Elementarnye rekursivnye funktsii, MTsNMO, M., 2003

[15] Pixley A. F., “The ternary discriminator function in universal algebra”, Math. Ann., 191 (1971), 167–180 | DOI | MR | Zbl