Refine
Year of publication
Document Type
- Article (20)
- Monograph/Edited Volume (1)
- Habilitation Thesis (1)
- Other (1)
Is part of the Bibliography
- yes (23)
Keywords
- formal languages (3)
- Automata systems (2)
- Lindenmayer systems (2)
- cooperating systems (2)
- (k,l)-Local language (1)
- 2-tag system (1)
- Accepting Grammars (1)
- Akzeptierende Grammatiken (1)
- Biologically inspired formal systems (1)
- Computing with DNA (1)
- Controlled Derivations (1)
- DNA hairpin formation (1)
- Decidability (1)
- Descriptional complexity (1)
- Finite automata (1)
- Formal languages (1)
- Gesteuerte Ableitungen (1)
- Grammar Systems (1)
- Grammatiksysteme (1)
- Hairpin completions (1)
- Hairpin reductions (1)
- Hiding processor (1)
- L systems (1)
- LBA problem (1)
- Leftmost Derivations (1)
- Linksableitungen (1)
- Multiple interpretation scheme (1)
- Operation problem (1)
- Parsing (1)
- Picture (1)
- Picture matching (1)
- Picture processor (1)
- Polarization (1)
- Reversibility (1)
- Semilinearity property (1)
- Splicing (1)
- Splicing processor (1)
- Systems of parallel communicating (1)
- Turing machine (1)
- Unary languages (1)
- accepting grammars (1)
- automata (1)
- context-free grammar (1)
- context-sensitive (1)
- decidability questions (1)
- degree of non-context-freeness (1)
- degree of non-regularity (1)
- degree of non-regulation (1)
- determinism (1)
- developmental systems (1)
- external ambiguity (1)
- finite state sequential transducers (1)
- grammar (1)
- internal ambiguity (1)
- leftmost derivations (1)
- o-ambiguity (1)
- parallel rewriting (1)
- programmed grammars (1)
- regular language (1)
- restricted parallelism (1)
- state complexity (1)
- theory of computation (1)
Institute
Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes.
We investigate the operation problem for linear and deterministic context-free languages: Fix an operation on formal languages. Given linear (deterministic, respectively) context-free languages, is the application of this operation to the given languages still a linear (deterministic, respectively) context-free language? Besides the classical operations, for which the linear and deterministic context-free languages are not closed, we also consider the recently introduced root and power operation. We show non-semidecidability, to be more precise, we show completeness for the second level of the arithmetic hierarchy for all of the aforementioned operations, except for the power operation, if the underlying alphabet contains at least two letters. The result for the power opera, tion solves an open problem stated in Theoret. Comput. Sci. 314 (2004) 445-449