Reconstructing Words from a σ-palindromic Language

被引：0

作者：

Brlek, Srecko ^{[1
]}

Lafreniere, Nadia ^{[1
]}

机构：

[1] Univ Quebec, Lab Combinatoire & Informat Math, Montreal, PQ H3C 3P8, Canada

来源：

FUNDAMENTA INFORMATICAE | 2014年 / 135卷 / 1-2期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Generalized palindromes; complexity; sigma-palindromic lacunas; sigma-palindromic defect; COMBINATORIAL PROPERTIES; OPERATORS;

D O I：

10.3233/FI-2014-1112

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We consider words on a finite alphabet Sigma and study the structure of its sigma- palindromes, i.e. words omega satisfying omega = sigma((omega) over tilde) for some involution sigma on the alphabet. We provide algorithms for the computation of sigma-lacunas in omega, that is the positions where the longest sigma-palindromic suffix is not uni-occurrent. The sigma-palindromic defect is explicitly computed for Sturmian words and the Thue-Morse word. Finally, the problem of reconstructing words from a given fixed set of sigma-palindromes is decidable.

引用

页码：59 / 72

页数：14

共 50 条

[21] The Boolean Language of Thought is recoverable from learning data
Carcassi, Fausto
Szymanik, Jakub
COGNITION, 2023, 239
[22] Reconstructing the Foundations of Joined-UpWorking: From Organisational Reform towards a Joint Engagement of Child and Family Services
Roets, Griet
Roose, Rudi
Schiettecat, Tineke
Vandenbroeck, Michel
BRITISH JOURNAL OF SOCIAL WORK, 2016, 46 (02) : 306 - 322
[23] Natural Language Processing to Extract Contextual Structure from Requirements
Vierlboeck, Maximilian
Dunbar, Daniel
Nilchiani, Roshanak
SYSCON 2022: THE 16TH ANNUAL IEEE INTERNATIONAL SYSTEMS CONFERENCE (SYSCON), 2022,
[24] The challenges of viewpoint-taking when learning a sign language: Data from the 'frog story' in British Sign Language
Gulamani, Sannah
Marshall, Chloe
Morgan, Gary
SECOND LANGUAGE RESEARCH, 2022, 38 (01) : 55 - 87
[25] First language attrition and second language attainment of Mandarin-speaking immigrants in Hong Kong: Evidence from prosodic focus
Yang, Yike
LANGUAGE ACQUISITION, 2023, 30 (02) : 201 - 203
[26] If I change the world changes: Language teaching from an emergentistic perspective
Leffa, Vilson J.
CALIDOSCOPIO, 2009, 7 (01): : 24 - 29
[27] Statistics of Language Morphology Change: From Biconsonantal Hunters to Triconsonantal Farmers
Agmon, Noam
Bloch, Yigal
PLOS ONE, 2013, 8 (12):
[28] Automatically Generating Precise Oracles from Structured Natural Language Specifications
Motwani, Manish
Brun, Yuriy
2019 IEEE/ACM 41ST INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING (ICSE 2019), 2019, : 188 - 199
[29] The emergence of embedded structure: insights from Kafr Qasem Sign Language
Kastner, Itamar
Meir, Irit
Sandler, Wendy
Dachkovsky, Svetlana
FRONTIERS IN PSYCHOLOGY, 2014, 5
[30] Canalization of Language Structure From Environmental Constraints: A Computational Model of Word Learning From Multiple Cues
Monaghan, Padraic
TOPICS IN COGNITIVE SCIENCE, 2017, 9 (01) : 21 - 34

← 1 2 3 4 5 →