MSO with tests and reducts

Tim Fernando, David Woods, Carl Vogel


Abstract
Tests added to Kleene algebra (by Kozen and others) are considered within Monadic Second Order logic over strings, where they are likened to statives in natural language. Reducts are formed over tests and non-tests alike, specifying what is observable. Notions of temporal granularity are based on observable change, under the assumption that a finite set bounds what is observable (with the possibility of stretching such bounds by moving to a larger finite set). String projections at different granularities are conjoined by superpositions that provide another variant of concatenation for Booleans.
Anthology ID:
W19-3106
Volume:
Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing
Month:
September
Year:
2019
Address:
Dresden, Germany
Venues:
FSMNLP | WS
SIG:
SIGFSM
Publisher:
Association for Computational Linguistics
Note:
Pages:
27–36
Language:
URL:
https://aclanthology.org/W19-3106
DOI:
10.18653/v1/W19-3106
Bibkey:
Cite (ACL):
Tim Fernando, David Woods, and Carl Vogel. 2019. MSO with tests and reducts. In Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing, pages 27–36, Dresden, Germany. Association for Computational Linguistics.
Cite (Informal):
MSO with tests and reducts (Fernando et al., 2019)
Copy Citation:
PDF:
https://aclanthology.org/W19-3106.pdf