Decidable and Undecidable Fragments of First-Order Concatenation Theory

Kristiansen, Lars; Murwanashyaka, Juvenal
Chapter; AcceptedVersion; Peer reviewed
View/Open
Year
2018
Permanent link
http://urn.nb.no/URN:NBN:no-72818

CRIStin
1612807

Is part of
Lecture Notes in Computer Science
Metadata
Show metadata
Appears in the following Collection
Original version
Sailing Routes in the World of Computation. 2018, 244-253, DOI: https://doi.org/10.1007/978-3-319-94418-0_25
Abstract
We identify a number of decidable and undecidable fragments of first-order concatenation theory. We also give a purely universal axiomatization which is complete for the fragments we identify. Furthermore, we prove some normal-form results.

This is a post-peer-review, pre-copyedit version of an article. The final authenticated version is available online at: https://link.springer.com/