Automata for unordered trees

DOI10.1016/j.ic.2016.07.012zbMath1362.68128OpenAlexW2481729132MaRDI QIDQ515668

Vincent Hugot, Ralf Treinen, Adrien Boiret, Joachim Niehren

Publication date: 16 March 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01179493/file/DeterministicAutomataUnordered_Journal-1.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Logics for unordered trees with data constraints ⋮ Presburger Büchi tree automata with applications to logics with expressive counting

Uses Software

• XPath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multitree automata that count
• Semigroups, Presburger formulas, and languages
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Logics for Unordered Trees with Data Constraints on Siblings
• Static and dynamic semantics of NoSQL languages
• Integer Vector Addition Systems with States
• On the complexity of integer programming
• Feature-constraint logics for unification grammars
• Records for logic programming
• Feature automata and recognizable sets of feature trees
• Chrobak Normal Form Revisited, with Applications
• Complexity of Problems of Commutative Grammars
• Automata, Languages and Programming
• Database Programming Languages
• Monadic datalog and the expressive power of languages for Web information extraction
• On Context-Free Languages
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Term Rewriting and Applications
• Rewriting Techniques and Applications