Complexity results on register context-free grammars and related formalisms

DOI10.1016/j.tcs.2022.04.055OpenAlexW4225384127MaRDI QIDQ2672616

Hiroyuki Seki, Yoshiaki Takata, Ryoma Senda

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.04.055

zbMATH Keywords

computational complexitydata languagedata wordregister context-free grammarregister pushdown automatonregister tree automaton

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Elements of finite model theory.
• On the freeze quantifier in Constraint LTL: Decidability and complexity
• Finite-memory automata
• Context-free languages over infinite alphabets
• Intractability of decision problems for finite-memory automata
• Complexity results on register context-free grammars and register tree automata
• A logical characterization of data languages.
• Generalized register context-free grammars
• Regular expressions for data words
• Alternating register automata on finite words and trees
• LTL with the freeze quantifier and register automata
• Two-variable logic on data words
• Querying Graphs with Data
• Two-variable logic on data trees and XML reasoning
• Automata and Logics for Words and Trees over an Infinite Alphabet
• Alternation
• Finite state machines for strings over infinite alphabets
• Tree Automata over Infinite Alphabets
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity results on register context-free grammars and related formalisms