6533b7dcfe1ef96bd1272a2d

RESEARCH PRODUCT

The Expressibility of Languages and Relations by Word Equations

Wojciech PlandowskiFilippo MignosiJuhani Karhumäki

subject

business.industryComputer scienceFormal languageComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Artificial intelligenceArithmeticbusinesscomputer.software_genrecomputerComputer Science::Formal Languages and Automata TheoryNatural language processingWord (computer architecture)

description

Classically, several properties and relations of words, such as being a power of a same word, can be expressed by using word equations. This paper is devoted to study in general the expressive power of word equations. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, the primitiveness and the equal length are such properties, as well as being any word over a proper subalphabet.

yearjournalcountryeditionlanguage
1997-01-01
10.1007/3-540-63165-8_168http://hdl.handle.net/11697/14322