×
Semenov, A. L.

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

Sib. Math. J. 18, 289-300 (1977).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0411.03054

Cited in 1 Review
Cited in 20 Documents

MSC:

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

Keywords:

regular predicates; definability in first-order languages; monadic predicate; Presburger predicate; two number system; first-order arithmetic; finite automata

Citations:

Zbl 0369.02023
PDF BibTeX XML Cite
\textit{A. L. Semenov}, Sib. Math. J. 18, 289--300 (1977; Zbl 0411.03054)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[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.