On Pebble Automata for Data Languages with Decidable Emptiness Problem
From MaRDI portal
Publication:3182968
DOI10.1007/978-3-642-03816-7_60zbMath1200.68150arXiv0910.5844OpenAlexW3006217603MaRDI 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
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)
Related Items
A note on the emptiness problem for alternating finite-memory automata, On pebble automata for data languages with decidable emptiness problem
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