Titlebook: Developments in Language Theory; 19th International C Igor Potapov Conference proceedings 2015 Springer International Publishing Switzerlan

不出名

Deciding Proper Conjugacy of Classes of One-Sided Finite-Type-Dyck Shifts, shifts constitute a subclass of these sets of sequences. A (one-sided) finite-type-Dyck shift is defined as the set of infinite sequences avoiding both some finite set of words and some finite set of matching patterns. We prove that proper conjugacy is decidable for a large class of one-sided finit

Spartan

Transfinite Lyndon Words,e exists a unique factorization in Lyndon words that are locally decreasing, a relaxation of the condition used in the case of finite words..In a second part, we prove that the factorization of a rational word has a special form and that it can be computed in polynomial time from a rational expressi

Benign

Unary Patterns with Permutations,idance of patterns with palindromes, avoidance of powers under coding, and other questions of recent interest. Unary patterns with permutations have been previously analysed only for lengths up to 3. Consider a pattern ., with ., . a word variable over an alphabet . and . function variables, to be r

Intellectual

Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change,c formulas that connect properties of successive letters. In the second, the letters are considered as columns of a labeled grid which an automaton traverses column by column. Thus, both models focus on the comparison of successive letters, i.e. “local changes”. We prove closure (and non-closure) pr

真实的你

expeditious

conceal

*-Continuous Kleene ,-Algebras,module and an infinite product operation that is also .-continuous. We show that .-continuous Kleene .-algebras give rise to iteration semiring-semimodule pairs, and that for Büchi automata over .-continuous Kleene .-algebras, one can compute the associated infinitary power series.

cortex

intuition

ORBIT

Hypothesis-Driven Simulation Studiestion “up to permutation” and “up to subset”. Although all these variations have been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up to now. We also consider the length of the shortest word . having the desired property.