Titlebook: Language and Automata Theory and Applications; 12th International C Shmuel Tomi Klein,Carlos Martín-Vide,Dana Shapira Conference proceeding

Breach

Descriptional and Computational Complexity of the Circuit Representation of Finite Automata,complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.

袖章

A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)sequential Transducers,hese problems can be efficiently solved for a large class of monoids that includes the free monoids, tropical monoid, and groups, and is closed under Cartesian Product. We describe this class of monoids in terms of five simple axioms. The first four of them seem to be natural. For the last one, we show that it is also necessary.

Abduct

Ganglion

Measuring Closeness Between Cayley Automatic Groups and Automatic Groups,l characteristic. We characterize Cayley automatic groups which are not automatic in terms of this numerical characteristic and then study it for the lamplighter group, the Baumslag–Solitar groups and the Heisenberg group.

projectile

智力高

Myelin

Language and Automata Theory and Applications978-3-319-77313-1Series ISSN 0302-9743 Series E-ISSN 1611-3349

平息

Constraint Satisfaction Problems: Complexity and Algorithms,In this paper we briefly survey the history of the Dichotomy Conjecture for the Constraint Satisfaction problem, that was posed 25 years ago by Feder and Vardi. We outline some of the approaches to this conjecture, and then describe an algorithm that yields an answer to the conjecture.

眼界

handle