Titlebook: Developments in Language Theory; 18th International C Arseny M. Shur,Mikhail V. Volkov Conference proceedings 2014 Springer International P

micturition

Upper Bounds on Syntactic Complexity of Left and Two-Sided Idealsd language with . left quotients (that is, with state complexity .) is at most .. + . − 1, and that of a two-sided ideal or a factor-closed language is at most .. + (. − 2)2. + 1. Since these bounds are known to be reachable, this settles the problems.

SEVER

On the Average Complexity of Brzozowski’s Algorithm for Deterministic Automata with a Small Number oes. We show that, as in the case of the uniform distribution, the average complexity is super-polynomial even if we consider random deterministic automata with only one final state. We therefore go beyond the previous study where the number of final states was linear in the number of states. Our result holds for alphabets with at least 3 letters.

细颈瓶

State Complexity of Deletion complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is . ·2. (respectively, .) when using complete (respectively, incomplete) deterministic finite automata.

一个搅动不安

On Two Algorithmic Problems about Synchronizing Automata problem is to decide whether a given reachable partial automaton is synchronizing. The second one is, given an .-state binary complete synchronizing automaton, to compute its reset threshold within performance ratio less than . ln (.) for a specific constant . > 0.

侵略者

Synchronizing Automata with Random Inputsynchronization is exponential in the number of states. At the same time, we show that the expected number of letters to synchronize any pair of the famous Černý automata is at most cubic in the number of states.

Gratulate

尽管

cinder

-Abelian Pattern Matchinge algorithm for identifying all occurrences of factors in a text that are .-abelian equivalent to some pattern .. Moreover, an optimal algorithm for finding the largest . for which two words are .-abelian equivalent is given. Solutions for various online versions of the .-abelian pattern matching problem are also proposed.

Dungeon

要控制

On Automatic Transitive GraphsWe study infinite automatic transitive graphs. In particular we investigate automaticity of certain Cayley graphs. We provide examples of infinite automatic transitive graphs that are not Cayley graphs. We prove that Cayley graphs of Baumslag–Solitar groups and the restricted wreath products of automatic transitive graphs with ℤ are automatic.