An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet

DOI10.2168/LMCS-4(1:8)2008zbMath1149.03014OpenAlexW3102786666MaRDI QIDQ3518274

Alexis Bès

Publication date: 7 August 2008

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-4(1:8)2008

zbMATH Keywords

first-order logicmonadic second-order logicdecidabilityfinite automatoncomposition theoreminfinite alphabetlogical structuredefinability in logicrecognizability by automatonrelationship between definability and recognizabilityFeferman-Vaught method

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Second- and higher-order model theory (03C85)

Related Items (6)

Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change ⋮ Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change ⋮ Symbolic tree automata ⋮ $$\mathbb {N}$$ -Memory Automata over the Alphabet $$\mathbb {N}$$ ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.

This page was built for publication: An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet