On Pebble Automata for Data Languages with Decidable Emptiness Problem
From MaRDI portal
Publication:3182968
DOI10.1007/978-3-642-03816-7_60zbMath1200.68150arXiv0910.5844MaRDI QIDQ3182968
Publication date: 16 October 2009
Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0910.5844
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03B25: Decidability of theories and sets of sentences
Related Items
On pebble automata for data languages with decidable emptiness problem, A note on the emptiness problem for alternating finite-memory automata
Cites Work
- Finite-memory automata
- Undecidable problems in unreliable computations.
- Verifying lossy channel systems has nonprimitive recursive complexity.
- Two-variable logic on data words
- Graph Reachability and Pebble Automata over Infinite Alphabets
- A Note on Two-pebble Automata Over Infinite Alphabets
- Automata and Logics for Words and Trees over an Infinite Alphabet
- Expressive Power of Pebble Automata
- Finite state machines for strings over infinite alphabets
- On Notions of Regularity for Data Languages