Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1158.03007
Choffrut, Christian
Deciding whether a relation defined in Presburger logic can be defined in weaker logics. (English)
[J] Theor. Inform. Appl. 42, No. 1, 121-135 (2008). ISSN 0988-3754; ISSN 1290-385X/e

The author defines a structure ${\cal M}_2$ to be decidable in a structure ${\cal M}_1$ (for ${\cal M}_1$, ${\cal M}_2$ on the same domain and such that each basic relation of ${\cal M}_2$ is definable in ${\cal M}_1$) if it is decidable for a relation first-order definable in ${\cal M}_1$ whether it is first-order definable in ${\cal M}_2$. For ${\cal M}_1$ being Presburger arithmetic (both on $\Bbb N$ and $\Bbb Z$), he shows that all ${\cal M}_2$ built taking at least two of the three types of basic relations $(x\geq c)$, $(x-y\geq c)$ and $(x=b$ mod $a)$ are decidable in Presburger arithmetic.
[Roger Villemaire (Montréal)]

MSC 2000:: *03B25 Decidability of theories and sets of sentences
03B10 First-order logic
03D05 Automata theory in connection with logical questions
68Q45 Formal languages

Keywords: decidability; Presburger arithmetic; first-order logic

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]