Titlebook: Developments in Language Theory; 14th International C Yuan Gao,Hanlin Lu,Sheng Yu Conference proceedings 2010 Springer-Verlag Berlin Heidel

Decimate

使成波状

On Decision Problems for Simple and Parameterized MachinesWe introduce what we believe to be the simplest known classes of language acceptors for which we can prove that decision problems (like universe, disjointness, containment, etc.) are undecidable. We also look at classes with undecidable decision problems and show that the problems become decidable for the “parameterized” versions of the machines.

BLANC

Computing Blocker Sets for the Regular Post Embedding ProblemBlocker and coblocker sets are regular languages involved in the algorithmic solution of the Regular Post Embedding Problem. We investigate the computability of these languages and related decision problems.

essential-fats

Reaction Systems: A Model of Computation Inspired by Biochemistryture. In other words, natural computing investigates models and computational techniques inspired by nature as well as it investigates, in terms of information processing, processes taking place in nature.

OMIT

On a Conjecture by Carpi and D’Alessandros for synchronizing automata with . states. We refute this conjecture as well as a related conjecture by Rystsov [13] and suggest a weaker version that still suffices to achieve a quadratic upper bound.

畏缩

FLIT

Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Latti and for finite and infinite words. This extends classical results of Kleene and Büchi to arbitrary bounded lattices, without any distributivity assumption that is fundamental in the theory of weighted automata over semirings. In fact, we obtain these results for large classes of strong bimonoids which properly contain all bounded lattices.

粘连

Minimization of Deterministic Bottom-Up Tree Transducerss based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.

fodlder

https://doi.org/10.1007/978-3-642-14455-4automata theory; complexity; computability; game theory; infinite words; inite automata; logic; tar; tempora