2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2021, p.1-13
2021
Volltextzugriff (PDF)
Details
- Autor(en) / Beteiligte
- Titel
- Positive first-order logic on words
- Ist Teil von
- 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2021, p.1-13
- Ort / Verlag
- Piscataway, NJ, USA: IEEE Press
- Erscheinungsjahr
- 2021
- Quelle
- ACM Digital Library
- Beschreibungen/Notizen
- We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is an FO-definable language that is monotone in monadic predicates but not definable in FO+. This provides a simple proof that Lyndon's preservation theorem fails on finite structures. We additionally show that given a regular language, it is undecidable whether it is definable in FO+.
- Sprache
- Englisch
- Identifikatoren
- ISBN: 9781665448956, 1665448954DOI: 10.1109/LICS52264.2021.9470602Titel-ID: cdi_ieee_primary_9470602
- Format
- –
- Schlagworte
- Automata, Computer science, Cost function, Mathematics of computing, Software and its engineering, Theory of computation, Theory of computation -- Computational complexity and cryptography, Theory of computation -- Formal languages and automata theory, Theory of computation -- Formal languages and automata theory -- Formalisms, Theory of computation -- Logic, Theory of computation -- Models of computation, Theory of computation -- Models of computation -- Computability, Theory of computation -- Semantics and reasoning, Theory of computation -- Theory and algorithms for application domains, Theory of computation -- Theory and algorithms for application domains -- Machine learning theory, Theory of computation -- Theory and algorithms for application domains -- Machine learning theory -- Reinforcement learning, Theory of computation -- Theory and algorithms for application domains -- Machine learning theory -- Reinforcement learning -- Sequential decision making