On pebble automata for data languages with decidable emptiness problem

DOI10.1016/J.JCSS.2010.03.004MaRDI QIDQ1959427zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On Pebble Automata for Data Languages with Decidable Emptiness Problem
• A note on two-pebble automata over infinite alphabets
• Complexity of Pebble Tree-Walking Automata
• scientific article; zbMATH DE number 6109856
• Pebble-intervals automata and \(\text{FO}^2\) with two orders

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1948151 (Why is no real title available?)
• A note on two-pebble automata over infinite alphabets
• Automata and Logics for Words and Trees over an Infinite Alphabet
• CONCUR 2004 - Concurrency Theory
• Expressive Power of Pebble Automata
• Finite state machines for strings over infinite alphabets
• Finite-memory automata
• Graph reachability and pebble automata over infinite alphabets
• Inconsistency Tolerance
• LTL with the freeze quantifier and register automata
• On Notions of Regularity for Data Languages
• On Pebble Automata for Data Languages with Decidable Emptiness Problem
• On Reasoning About Rings
• Two-variable logic on data words
• Undecidable problems in unreliable computations.
• Verifying lossy channel systems has nonprimitive recursive complexity.

Cited in

(8)

• A note on the emptiness problem for alternating finite-memory automata
• On Pebble Automata for Data Languages with Decidable Emptiness Problem
• Subsequence versus substring constraints in sequence pattern languages
• Reachability in pushdown register automata
• Set augmented finite automata over infinite alphabets
• A note on two-pebble automata over infinite alphabets
• On temporal logics with data variable quantifications: decidability and complexity
• Complexity hierarchies beyond elementary

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1959427)