Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.

DOI10.1016/j.tcs.2008.07.018zbMath1161.03025OpenAlexW2056054104MaRDI QIDQ1001895

Serge Grigorieff, Christian Choffrut

Publication date: 19 February 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.07.018

zbMATH Keywords

first-order logicfinite automatainfinite alphabetssynchronous relations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70)

Related Items

The decision problem for some logics for finite words on infinite alphabets ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata

Cites Work

• Infinite trees and automaton-definable relations over \(\omega\)-words
• Sets recognized by n-tape automata
• Two-variable logic on data words
• Definable relations and first-order query languages over strings
• An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet
• Regular prefix relations
• Monadic second order definable relations on the binary tree
• Model Checking Freeze LTL over One-Counter Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.