Titlebook: Language and Automata Theory and Applications; Second International Carlos Martín-Vide,Friedrich Otto,Henning Fernau Conference proceedings

检查

Random Context in Regulated Rewriting , Cooperating Distributed Grammar Systemse random context grammars. In particular, the language families generated by CD grammar systems working in the .- and -modes of derivation obey a characterization in terms of ET0L systems, or equivalently by context-free disjoint forbidding random context grammars, and of context-free random context

Interim

Bombast

Induced Subshifts and Cellular Automatamata and, while observing that the new automaton can model a different abstract dynamics, we remark several properties that are shared with the old one. After that, we simulate the old automaton inside the new one, and discuss some consequences and restrictions.

lavish

推崇

Consensual Definition of Languages by Regular Setsstrings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet can be interpreted as defining another language over the unmarked alphabet, called the consensual la

glucagon

粘土

On Bifix Systems and Generalizationsrelation to the condition that regularity of sets is preserved, resp. that the derivation relation is even rational. Finally, we compare our model to ground tree rewriting systems and exhibit some differences.

locus-ceruleus

The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Res are parsimonious, it follows that the problems Unique-3-TRP and Unique-2-TRP are DP-complete under randomized reductions. Finally, we prove that the infinite variants of 3-TRP and 2-TRP are undecidable.

cancer

Deterministic Input-Reversal and Input-Revolving Finite Automataudied are not closed under standard operations. In particular, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.

incite

Extending the Overlap Graph for Gene Assembly in Ciliatesing system. Finally, we give characterizations of the ‘power’ of both types of graph rewriting rules. Because of the equivalence of these string and graph rewriting systems, the given characterizations can be carried over to the string rewriting system.