Presburgerness of predicates regular in two number systems. (English) Zbl 0411.03054


03F30 First-order arithmetic and fragments
03B25 Decidability of theories and sets of sentences
03B10 Classical first-order logic
03D05 Automata and formal grammars in connection with logical questions


Zbl 0369.02023
Full Text: DOI


[1] A. L. Semenov, ?Presburgerness of sets recognizable by finite automata in two number systems,? Third All-Union Conference of Mathematical Logic. Reports Abstracts [in Russian], Izd. Inst. Math. Sib. Otdel. Akad. Nauk SSSR, Novosibirsk (1974), pp. 201-203.
[2] J. R. Büchi, ?Weak second-order arithmetic and finite automata,? Z. Math. Logik Grundl. Math.,6, No. 1, 66-92 (1960); Kiberneticheskii Sb., No. 8, 42-77 (1964). · Zbl 0103.24705
[3] A. Cobham, ?On the base-dependence of sets of numbers, recognizable by finite automata,? Math. Systems Theory,3, No. 2, 186-192 (1969); Kiberneticheskii Sb., Nov. Ser., No. 8, 62-71 (1971). · Zbl 0179.02501
[4] S. Ginsburg and E. H. Spanier, ?Semigroups, Presburger formulas and languages,? Pac. J. Math.,13, No. 4, 570-581 (1966). · Zbl 0143.01602
[5] J. W. Thatcher, ?Decision problems for multiple successor arithmetics,? J. Symbolic Logic,31, No. 2, 182-190 (1966). · Zbl 0144.00106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.