An Extension of Data Automata that Captures XPath
The work
| Authors | Mikołaj Bojańczyk; Sławomir Lasota |
|---|---|
| Editors | |
| Type | misc |
| Year | 2010 |
| Citekey | bojanczyk2010extension |
Where it appeared
| Published in | Proceedings - Symposium on Logic in Computer Science |
|---|---|
| Publisher | Institute of Electrical and Electronics Engineers |
| Pages | 243--252 |
Identifiers
| DOI | 10.1109/lics.2010.33 |
|---|---|
| OpenAlex | W2157277195 |
Access
| Landing page | https://doi.org/10.1109/lics.2010.33 |
|---|
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
We define a new kind of automata recognizing properties of data words or data trees and prove that the automata capture all queries definable in Regular XPath. We show that the automata-theoretic approach may be applied to answer decidability and expressibility questions for XPath. Finally, we use the newly introduced automata as a common framework to classify existing automata on data words and trees, including data automata, register automata and alternating register automata.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-10-24 16:01 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Cite it as
@misc{bojanczyk2010extension,
title = {An Extension of Data Automata that Captures XPath},
author = {Mikołaj Bojańczyk and Sławomir Lasota},
year = {2010},
journal = {Proceedings - Symposium on Logic in Computer Science},
publisher = {Institute of Electrical and Electronics Engineers},
pages = {243--252},
doi = {10.1109/lics.2010.33},
}
This record lives at https://refs.drheap.org/bojanczyk2010extension/ and will keep doing so.