Formal Languages, Automaton and Numeration Systems presents readers
with a review of research related to formal language theory,
combinatorics on words or numeration systems, such as Words, DLT
(Developments in Language Theory), ICALP, MFCS (Mathematical
Foundation of Computer Science), Mons Theoretical Computer Science
Days, Numeration, CANT (Combinatorics, Automata and Number
Theory).Combinatorics on words deals with problems that can be
stated in a non-commutative monoid, such as subword complexity of
finite or infinite words, construction and properties of infinite
words, unavoidable regularities or patterns. When considering some
numeration systems, any integer can be represented as a finite word
over an alphabet of digits. This simple observation leads to the
study of the relationship between the arithmetical properties of
the integers and the syntactical properties of the corresponding
representations. One of the most profound results in this direction
is given by the celebrated theorem by Cobham. Surprisingly, a
recent extension of this result to complex numbers led to the
famous Four Exponentials Conjecture. This is just one example of
the fruitful relationship between formal language theory (including
the theory of automata) and number theory.Contents to include: -
algebraic structures, homomorphisms, relations, free monoid -
finite words, prefixes, suffixes, factors, palindromes- periodicity
and Fine-Wilf theorem- infinite words are sequences over a finite
alphabet- properties of an ultrametric distance, example of the
p-adic norm- topology of the set of infinite words- converging
sequences of infinite and finite words, compactness argument-
iterated morphism, coding, substitutive or morphic words- the
typical example of the Thue-Morse word- the Fibonacci word, the Mex
operator, the n-bonacci words-
wordscomingfromnumbertheory(baseexpansions, continuedfractions,
...) - the taxonomy of Lindenmayer systems- S-adic sequences,
Kolakoski word- repetition in words, avoiding repetition,
repetition threshold- (complete) de Bruijn graphs- concepts from
computability theory and decidability issues- Post correspondence
problem and application to mortality of matrices- origins of
combinatorics on words- bibliographic notes- languages of finite
words, regular languages- factorial, prefix/suffix closed
languages, trees and codes- unambiguous and deterministic automata,
Kleene's theorem- growth function of regular languages-
non-deterministic automata and determinization- radix order, first
word of each length and decimation of a regular language- the
theory of the minimal automata- an introduction to algebraic
automata theory, the syntactic monoid and thesyntactic complexity-
star-free languages and a theorem of Schu ̈tzenberger- rational
formal series and weighted automata- context-free languages,
pushdown automata and grammars- growth function of context-free
languages, Parikh's theorem- some decidable and undecidable
problems in formal language theory- bibliographic notes- factor
complexity, Morse-Hedlund theorem- arithmetic complexity, Van Der
Waerden theorem, pattern complexity - recurrence, uniform
recurrence, return words- Sturmian words, coding of rotations,
Kronecker's theorem- frequencies of letters, factors and primitive
morphism- critical exponent- factor complexity of automatic
sequences- factor complexity of purely morphic sequences- primitive
words, conjugacy, Lyndon word- abelianisation and abelian
complexity- bibliographic notes- automatic sequences, equivalent
definitions- a theorem of Cobham, equivalence of automatic
sequences with constantlength morphic sequences- a few examples of
well-known automatic sequences- about Derksen's theorem- some
morphic sequences are not automatic- abstract numeration system and
S-automatic sequences- k - ∞-automatic sequences- bibliographic
notes- numeration systems, greedy algorithm- positional numeration
systems, recognizable sets of integers- divisibility criterion and
recognizability of N- properties of k-recognizable sets of
integers, ratio and difference of consec-utive elements:
syndeticity- integer base and Cobham's theorem on the base
dependence of the recog-nizability- non-standard numeration systems
based on sequence of integers- linear recurrent sequences, Loraud
and Hollander results- Frougny's normalization result and addition-
morphic numeration systems/sets of integers whose characteristic
sequenceis morphic- towards a generalization of Cobham's theorem- a
few words on the representation of real numbers, β-integers,
finitenessproperties- automata associated with Parry numbers and
numeration systems- bibliographic notesFirst order logic-
Presburger arithmetic and decidable theory- Muchnik's
characterization of semi-linear sets- Bu ̈chi's theorem:
k-recognizable sets are k-definable - extension to Pisot numeration
systems- extension to real numbers- decidability issues for
numeration systems- applications in combinatorics on words
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!
Welcome to Loot.co.za!
Sign in / Register |Wishlists & Gift Vouchers |Help | Advanced search
