scientific article

zbMath0487.68064MaRDI QIDQ3948609

Arto Salomaa

Publication date: 1981

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

decidabilitycontext-free languagesregular languagesmorphismscodesrecursively enumerable languageequality setscoloring of graphsDOL-systemselementary morphismsgrammatical familieslanguage familiesfamilies of graphsmorphic representationsDOL equivalence problemfinite power propertyrestriction of the star heightsentential forms of context-free languagesThue's problem

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (33)

Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices ⋮ PCP-prime words and primality types ⋮ Algorithmic ways of deciding whether an infinite language is a code ⋮ Caractérisation results about $L$ codes ⋮ A characterization of free pairs of upper triangular free monoid morphisms ⋮ On public-key cryptosystem based on Church-Rosser string-rewriting systems ⋮ Distance automata having large finite distance or finite ambiguity ⋮ A rewriting of Fife's theorem about overlap-free words ⋮ Exponential diophantine equations in rings of positive characteristic ⋮ Comparing descriptional and computational complexity of infinite words ⋮ Growth of positive words and lower bounds of the growth rate for Thompson’s groups F(p) ⋮ A linear-time algorithm to decide whether a binary word contains an overlap ⋮ Algebras of linear growth and the dynamical Mordell-Lang conjecture ⋮ Unnamed Item ⋮ Degrees of Infinite Words, Polynomials and Atoms ⋮ On the power of periodic iteration of morphisms ⋮ If a DOL language is k-power free then it is circular ⋮ Unnamed Item ⋮ A remark on morphic sturmian words ⋮ On the structure of some group codes ⋮ A periodicity property of iterated morphisms ⋮ Existence of words over three-letter alphabet not containing squares with replacement errors ⋮ Finite maximal codes and triangle conjecture ⋮ Abelian squares are avoidable on 4 letters ⋮ On characterizations of recursively enumerable languages ⋮ Detecting leftmost maximal periodicities ⋮ The Thue problem and logical specifications of derivation in formal systems ⋮ Existence of words over a binary alphabet free from squares with mismatches ⋮ Free subalgebras of Lie algebras close to nilpotent ⋮ On some variants of Post's correspondence problem ⋮ Symmetric graphs and interpretations ⋮ Unavoidable binary patterns ⋮ On simplest possible solutions for Post Correspondence Problems

This page was built for publication: