Talk:Alternation (formal language theory)
 | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
evidence for this usage?[edit]
I have never heard of this usage, and contend that "alternation" in formal language theory refers to alternating between existentials and universals -- see "Alternation" (Chandra & Stockmeyer 1976) and the various derived models of computation like Alternating finite automaton. The references only show this usage in pattern matching. If the article is about formal language theory, it should be called "Union (formal language theory)". If it's about pattern matching, I'm not sure it meets WP:Notability on its own outside of a discussion of other regex constructs. Caleb Stanford (talk) 14:26, 11 November 2021 (UTC)
- Resolved at Wikipedia:Articles for deletion/Union of two regular languages. References for this usage:
The following all use "alternation" in the sense of the union of formal languages: "LR-parsing of extended context free grammars", Madsen & Kristensen 1976, doi:10.1007/BF00265221; "A compact function for regular expression pattern matching", Richards 1979, doi:10.1002/spe.4380090703; "On String Pattern Matching: A New Model with a Polynomial Time Algorithm", Liu, 1981; doi:10.1137/0210010; "Finding Regular Simple Paths in Graph Databases", Mendelzon & Wood 1995, doi:10.1137/S009753979122370X; "Regular expression types for XML", Hosoya et al 2005, doi:10.1145/1053468.1053470; "String generation for testing regular expressions", Zheng et al 2020, doi:10.1093/comjnl/bxy137; and no doubt many others. —David Eppstein (talk) 20:46, 11 November 2021 (UTC)
Caleb Stanford (talk) 21:05, 11 November 2021 (UTC)