Alternating register automata on finite words and trees

DOI10.2168/LMCS-8(1:22)2012zbMath1238.68074arXiv1202.3957MaRDI QIDQ2881089

Diego Figueira

Publication date: 3 April 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.3957

zbMATH Keywords

XMLinfinite alphabetalternating tree register automatadata-treeforward XPathunranked ordered tree

Mathematics Subject Classification ID

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

Related Items (14)

Weighted Register Automata and Weighted Logic on Data Words ⋮ Reasoning about integrity constraints for tree-structured data ⋮ On temporal logics with data variable quantifications: decidability and complexity ⋮ Unnamed Item ⋮ Complexity results on register context-free grammars and related formalisms ⋮ Set augmented finite automata over infinite alphabets ⋮ Logics of Repeating Values on Data Trees and Branching Counter Systems ⋮ Extending two-variable logic on data trees with order on data values and its automata ⋮ Weighted register automata and weighted logic on data words ⋮ Automated Program Verification ⋮ On Freeze LTL with Ordered Attributes ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ The Containment Problem for Unambiguous Register Automata ⋮ Complexity Hierarchies beyond Elementary

Uses Software

• XPath

This page was built for publication: Alternating register automata on finite words and trees