On pebble automata for data languages with decidable emptiness problem

DOI10.1016/j.jcss.2010.03.004zbMath1208.68142OpenAlexW2042546332MaRDI QIDQ1959427

Tony Tan

Publication date: 7 October 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.03.004

zbMATH Keywords

decidabilityfinite state automatainfinite alphabet2-pebble automata3-pebble automata

Mathematics Subject Classification ID

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 (6)

On temporal logics with data variable quantifications: decidability and complexity ⋮ Reachability in pushdown register automata ⋮ Set augmented finite automata over infinite alphabets ⋮ A note on the emptiness problem for alternating finite-memory automata ⋮ Subsequence versus substring constraints in sequence pattern languages ⋮ Complexity Hierarchies beyond Elementary

Cites Work

• Unnamed Item
• Unnamed Item
• Finite-memory automata
• Undecidable problems in unreliable computations.
• Verifying lossy channel systems has nonprimitive recursive complexity.
• LTL with the freeze quantifier and register automata
• Two-variable logic on data words
• Graph Reachability and Pebble Automata over Infinite Alphabets
• On Pebble Automata for Data Languages with Decidable Emptiness Problem
• 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
• CONCUR 2004 - Concurrency Theory
• On Notions of Regularity for Data Languages
• Inconsistency Tolerance
• On Reasoning About Rings

This page was built for publication: On pebble automata for data languages with decidable emptiness problem