The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata

DOI10.1016/j.tcs.2009.01.034zbMath1173.68031OpenAlexW2073158691MaRDI QIDQ2271426

Serge Grigorieff, Christian Choffrut

Publication date: 7 August 2009

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

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

zbMATH Keywords

first-order logicmultitape automatafinite words over infinite alphabets

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equivalence problem of multitape finite automata
• Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
• Rational equivalence relations
• Infinite trees and automaton-definable relations over \(\omega\)-words
• Classical recursion theory. Vol. II
• Multitape one-way nonwriting automata
• 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
• On Relations Defined by Generalized Finite Automata

This page was built for publication: The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata