0000000000395415

AUTHOR

Juhani Karhumäki

showing 2 related works from this author

The Expressibility of Languages and Relations by Word Equations

1997

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.

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)
researchProduct

DEFECT THEOREMS FOR TREES

2000

We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However, as we show, the prefix rank forms an exception.

Discrete mathematicsPrefixCombinatoricsSet (abstract data type)Combinatorics on wordsAlgebra and Number TheoryComputational Theory and MathematicsInformationSystems_INFORMATIONSTORAGEANDRETRIEVALRank (graph theory)Computer Science::Formal Languages and Automata TheoryInformation SystemsTheoretical Computer ScienceMathematicsDevelopments In Language Theory
researchProduct