patternMinor
Have non-regular language classes of infinite words been studied?
Viewed 0 times
infinitestudiednonwordsregularlanguagebeenclasseshave
Problem
For regular languages we have $\omega$-regular languages which extend them to infinite words.
Are there such extensions for CFG's, CSG's and recursively enumerable languages?
Are there such extensions for CFG's, CSG's and recursively enumerable languages?
Solution
We have the following MSO characterization of regular nested word languages:
Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two unary predicates call and return, linear successor and the matching relation ↝.
The recommended reference on Nested Words and Visibly Pushdown Languages treats infinite words in section 8. Nested $\omega$-Words, and shows that the MSO characterization carries over:
Theorem 8.4 (MSO characterization of $\omega$-languages).
A language $L$ of nested $\omega$-words over $\Sigma$ is regular iff there is an MSO sentence $\varphi$ over $\Sigma$ that defines $L$.
Because often deterministic CFGs are actually visibly pushdown languages, this covers a huge portion of the practically relevant CFGs. Moreover, this even provides a context where considering $\omega$-languages is practically relevant, as explained in the same section of the reference.
Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two unary predicates call and return, linear successor and the matching relation ↝.
The recommended reference on Nested Words and Visibly Pushdown Languages treats infinite words in section 8. Nested $\omega$-Words, and shows that the MSO characterization carries over:
Theorem 8.4 (MSO characterization of $\omega$-languages).
A language $L$ of nested $\omega$-words over $\Sigma$ is regular iff there is an MSO sentence $\varphi$ over $\Sigma$ that defines $L$.
Because often deterministic CFGs are actually visibly pushdown languages, this covers a huge portion of the practically relevant CFGs. Moreover, this even provides a context where considering $\omega$-languages is practically relevant, as explained in the same section of the reference.
Context
StackExchange Computer Science Q#45450, answer score: 4
Revisions (0)
No revisions yet.