The theory of concatenation over finite models

We propose FC, a new logic on words that combines finite model theory with the theory of concatenation - a first-order logic that is based on word equations. Like the theory of concatenation, FC is built around word equations; in contrast to it, its semantics are defined to only allow finite models,...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-05
Main Authors: Freydenberger, Dominik D, Peterfreund, Liat
Format: Article
Language:English
Subjects:
Astronomical models
Information retrieval
Iterative methods
Semantics
Words (language)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose FC, a new logic on words that combines finite model theory with the theory of concatenation - a first-order logic that is based on word equations. Like the theory of concatenation, FC is built around word equations; in contrast to it, its semantics are defined to only allow finite models, by limiting the universe to a word and all its factors. As a consequence of this, FC has many of the desirable properties of FO on finite models, while being far more expressive than FO[
ISSN:2331-8422