@inproceedings{10.1007/978-3-030-02508-3_22,
    Abstract = {Register context-free grammars (RCFG) and register tree automata (RTA) are an extension of context-free grammars and tree automata, respectively, to handle data values in a restricted way. RTA are paid attention as a model of query languages for structured documents such as XML with data values. This paper investigates the computational complexity of the basic decision problems for RCFG and RTA. We show that the membership and emptiness problems for RCFG are EXPTIME-complete and also show how the complexity reduces by introducing subclasses of RCFG. The complexity of these problems for RTA are also shown to be NP-complete and EXPTIME-complete.},
    Address = {Cham},
    Author = {Senda, Ryoma and Takata, Yoshiaki and Seki, Hiroyuki},
    BookTitle = {Theoretical Aspects of Computing -- ICTAC 2018},
    Editor = {Fischer, Bernd and Uustalu, Tarmo},
    File = {Senda2018\_Chapter\_ComplexityResultsOnRegisterCon (0) - a - a - p.pdf},
    ISBN = {978-3-030-02508-3},
    Pages = {415--434},
    Publisher = {Springer International Publishing},
    Title = {Complexity Results on Register Context-Free Grammars and Register Tree Automata},
    Year = {2018},
    date-added = {2019-03-19 14:23:10 +0100},
    date-modified = {2019-03-19 14:23:10 +0100},
    doi = {10.1007/978-3-030-02508-3_22}
}

@inproceedings{10.1007/978-3-030-02508-3_22, Abstract = {Register context-free grammars (RCFG) and register tree automata (RTA) are an extension of context-free grammars and tree automata, respectively, to handle data values in a restricted way. RTA are paid attention as a model of query languages for structured documents such as XML with data values. This paper investigates the computational complexity of the basic decision problems for RCFG and RTA. We show that the membership and emptiness problems for RCFG are EXPTIME-complete and also show how the complexity reduces by introducing subclasses of RCFG. The complexity of these problems for RTA are also shown to be NP-complete and EXPTIME-complete.}, Address = {Cham}, Author = {Senda, Ryoma and Takata, Yoshiaki and Seki, Hiroyuki}, BookTitle = {Theoretical Aspects of Computing -- ICTAC 2018}, Editor = {Fischer, Bernd and Uustalu, Tarmo}, File = {Senda2018_Chapter_ComplexityResultsOnRegisterCon (0) - a - a - p.pdf}, ISBN = {978-3-030-02508-3}, Pages = {415--434}, Publisher = {Springer International Publishing}, Title = {Complexity Results on Register Context-Free Grammars and Register Tree Automata}, Year = {2018}, date-added = {2019-03-19 14:23:10 +0100}, date-modified = {2019-03-19 14:23:10 +0100}, doi = {10.1007/978-3-030-02508-3_22} }