Using Tree Automata and Regular Expressions to Manipulate Hierarchically Structured Data

Title: Using Tree Automata and Regular Expressions to Manipulate Hierarchically Structured Data

Abstract: This research paper proposes a simple and flexible formal data model for processing hierarchically structured data. Based on the concepts of finite automata and tree automata, it applies regular languages and expressions to structured strings, allowing for efficient manipulation of hierarchical data records. The paper compares these automata with classical string and tree automata, demonstrating that the model is a superset of the classical models. It discusses the unification of structural and content transformations, providing applications with a single data type. The research offers a generic alternative to ad-hoc approaches and outlines further research directions.

Research Question: How can we develop a simple and flexible formal data model for manipulating hierarchically structured data?

Methodology: The research uses concepts from finite automata and tree automata to create a data model for structured strings. It compares this model with classical string and tree automata, showing that it is a superset of the classical models. Regular languages and expressions are applied to the structured strings, enabling efficient manipulation of hierarchical data records.

Results: The research presents a data model that supports the hierarchical structuring of information. It demonstrates that the model is a superset of the classical string and tree automata models, allowing for greater flexibility and interoperability. Regular expressions and substitution, which have been widely used for efficient unstructured text processing, are applied to the model, enabling efficient manipulation of hierarchical data records.

Implications: The research provides a unified data model for structural and content transformations, simplifying the development of applications that deal with hierarchically structured data. It offers a generic alternative to ad-hoc approaches, promoting consistency and ease of use across various applications. The research also outlines further directions for future study, encouraging continued exploration in this area.

Link to Article: https://arxiv.org/abs/0201008v1 Authors: arXiv ID: 0201008v1