The decision problem for some logics for finite words on infinite alphabets

DOI10.1007/s10958-009-9407-1zbMath1179.03017OpenAlexW1963525214MaRDI QIDQ843605

Serge Grigorieff, Christian Choffrut

Publication date: 15 January 2010

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-009-9407-1

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Cites Work

• Unnamed Item
• Unnamed Item
• Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
• Model theory
• A course in model theory. An introduction to contemporary mathematical logic. Transl. from the French by Moses Klein
• Decision problems for semi-Thue systems with a few rules
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• Sets recognized by n-tape automata
• Definable relations and first-order query languages over strings
• Model Checking Freeze LTL over One-Counter Automata
• Decision problems for multiple successor arithmetics
• Concatenation as a basis for arithmetic