On the existential arithmetics with addition and bitwise minimum

DOI10.1007/978-3-031-30829-1_9OpenAlexW4366503913MaRDI QIDQ6091188

Mikhail R. Starchak

Publication date: 24 November 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-30829-1_9

zbMATH Keywords

recursively enumerable setsconcatenationParikh automataBüchi arithmeticexistential definabilitybitwise minimumDPR-theorem

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The decision problem for exponential diophantine equations
• A new proof of the theorem on exponential diophantine representation of enumerable sets
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Logic and \(p\)-recognizable sets of integers
• On the expressiveness of Büchi arithmetic
• Semigroups, Presburger formulas, and languages
• Expansions of MSO by cardinality relations
• Weak Second‐Order Arithmetic and Finite Automata
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Decision Problems of Finite Automata Design and Related Arithmetics
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
• Joining k- and l-recognizable sets of natural numbers
• On Context-Free Languages
• Arithmetical problems and recursively enumerable predicates

This page was built for publication: On the existential arithmetics with addition and bitwise minimum