Standard
On the Existential Arithmetics with Addition and Bitwise Minimum. / Старчак, Михаил Романович.
Foundations of Software Science and Computation Structures: 26th International Conference, FoSSaCS 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. ed. / Orna Kupferman; Pawel Sobocinski. Springer Nature, 2023. p. 176–195 (Lecture Notes in Computer Science; Vol. 13992).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Harvard
Старчак, МР 2023,
On the Existential Arithmetics with Addition and Bitwise Minimum. in O Kupferman & P Sobocinski (eds),
Foundations of Software Science and Computation Structures: 26th International Conference, FoSSaCS 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. Lecture Notes in Computer Science, vol. 13992, Springer Nature, pp. 176–195, 26th International Conference on Foundations of Software Science and Computation Structures, Paris, France,
24/04/23.
https://doi.org/10.1007/978-3-031-30829-1_9
APA
Старчак, М. Р. (2023).
On the Existential Arithmetics with Addition and Bitwise Minimum. In O. Kupferman, & P. Sobocinski (Eds.),
Foundations of Software Science and Computation Structures: 26th International Conference, FoSSaCS 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings (pp. 176–195). (Lecture Notes in Computer Science; Vol. 13992). Springer Nature.
https://doi.org/10.1007/978-3-031-30829-1_9
Vancouver
Старчак МР.
On the Existential Arithmetics with Addition and Bitwise Minimum. In Kupferman O, Sobocinski P, editors, Foundations of Software Science and Computation Structures: 26th International Conference, FoSSaCS 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. Springer Nature. 2023. p. 176–195. (Lecture Notes in Computer Science).
https://doi.org/10.1007/978-3-031-30829-1_9
Author
Старчак, Михаил Романович. /
On the Existential Arithmetics with Addition and Bitwise Minimum. Foundations of Software Science and Computation Structures: 26th International Conference, FoSSaCS 2023, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2023, Paris, France, April 22–27, 2023, Proceedings. editor / Orna Kupferman ; Pawel Sobocinski. Springer Nature, 2023. pp. 176–195 (Lecture Notes in Computer Science).
BibTeX
@inproceedings{c4d953c3a447437ebb5e8b592eeb73b4,
title = "On the Existential Arithmetics with Addition and Bitwise Minimum",
abstract = "This paper presents a similar approach for existential first-order characterizations of the languages recognizable by finite automata, by Parikh automata, and by multi-counter machines over the alphabet {0, 1,.., k- 1 }n for some k≥ 2. The set of k-FA-recognizable relations coincides with the set of relations, which are existentially definable in the structure, where corresponds to the bitwise minimum of base k. In order to obtain an existential first-order description of k-Parikh automata languages, we extend this structure with the predicate EqNZBk(x, y) which is true if and only if x and y have the same number of non-zero bits in k-ary encoding. Using essentially the same ideas, we encode computations of k-multi-counter machines and thus show that every recursively enumerable relation over the natural numbers is existentially definable in the aforementioned structure supplemented with concatenation z=x⌢ky⇌z=x+klk(x)y, where lk(x) is the bit-length of x in base k. This result gives us another proof of DPR-theorem.",
keywords = "Bitwise minimum, B{\"u}chi arithmetic, Concatenation, DPR-theorem, Existential definability, Parikh automata, Recursively enumerable sets",
author = "Старчак, {Михаил Романович}",
year = "2023",
month = apr,
day = "21",
doi = "10.1007/978-3-031-30829-1_9",
language = "English",
isbn = "978-3-031-30828-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "176–195",
editor = "Orna Kupferman and Pawel Sobocinski",
booktitle = "Foundations of Software Science and Computation Structures",
address = "Germany",
note = "null ; Conference date: 24-04-2023 Through 27-04-2023",
url = "https://etaps.org/2023/conferences/",
}
RIS
TY - GEN
T1 - On the Existential Arithmetics with Addition and Bitwise Minimum
AU - Старчак, Михаил Романович
N1 - Conference code: 26
PY - 2023/4/21
Y1 - 2023/4/21
N2 - This paper presents a similar approach for existential first-order characterizations of the languages recognizable by finite automata, by Parikh automata, and by multi-counter machines over the alphabet {0, 1,.., k- 1 }n for some k≥ 2. The set of k-FA-recognizable relations coincides with the set of relations, which are existentially definable in the structure, where corresponds to the bitwise minimum of base k. In order to obtain an existential first-order description of k-Parikh automata languages, we extend this structure with the predicate EqNZBk(x, y) which is true if and only if x and y have the same number of non-zero bits in k-ary encoding. Using essentially the same ideas, we encode computations of k-multi-counter machines and thus show that every recursively enumerable relation over the natural numbers is existentially definable in the aforementioned structure supplemented with concatenation z=x⌢ky⇌z=x+klk(x)y, where lk(x) is the bit-length of x in base k. This result gives us another proof of DPR-theorem.
AB - This paper presents a similar approach for existential first-order characterizations of the languages recognizable by finite automata, by Parikh automata, and by multi-counter machines over the alphabet {0, 1,.., k- 1 }n for some k≥ 2. The set of k-FA-recognizable relations coincides with the set of relations, which are existentially definable in the structure, where corresponds to the bitwise minimum of base k. In order to obtain an existential first-order description of k-Parikh automata languages, we extend this structure with the predicate EqNZBk(x, y) which is true if and only if x and y have the same number of non-zero bits in k-ary encoding. Using essentially the same ideas, we encode computations of k-multi-counter machines and thus show that every recursively enumerable relation over the natural numbers is existentially definable in the aforementioned structure supplemented with concatenation z=x⌢ky⇌z=x+klk(x)y, where lk(x) is the bit-length of x in base k. This result gives us another proof of DPR-theorem.
KW - Bitwise minimum
KW - Büchi arithmetic
KW - Concatenation
KW - DPR-theorem
KW - Existential definability
KW - Parikh automata
KW - Recursively enumerable sets
UR - https://www.mendeley.com/catalogue/401cf2de-86aa-3223-84a1-dc0a2087cadf/
U2 - 10.1007/978-3-031-30829-1_9
DO - 10.1007/978-3-031-30829-1_9
M3 - Conference contribution
SN - 978-3-031-30828-4
T3 - Lecture Notes in Computer Science
SP - 176
EP - 195
BT - Foundations of Software Science and Computation Structures
A2 - Kupferman, Orna
A2 - Sobocinski, Pawel
PB - Springer Nature
Y2 - 24 April 2023 through 27 April 2023
ER -
