Non-self-embedding linear context-free tree grammars generate regular tree languages
- Submitting institution
-
University of St Andrews
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 255251331
- Type
- D - Journal article
- DOI
-
-
- Title of journal
- Journal of Automata, Languages Combinatorics
- Article number
- -
- First page
- 203
- Volume
- 21
- Issue
- 3
- ISSN
- 1430-189X
- Open access status
- Compliant
- Month of publication
- December
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
A - Artificial Intelligence
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The classes of regular and context-free tree languages are fundamental to applications of natural language processing such as machine translation. Knowing whether a language falls into one or the other class is important because it determines the kinds of processing that can be done. The new theoretical result, which relies on innovative proof techniques, gives an original characterization of one class in terms of the other. It was the starting point for the PhD thesis: Markus Teichmann, "Expressing Context-Free Tree Languages by Regular Tree Grammars", TU Dresden, 2016.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
