Institut für Informatik und Computational Science
Refine
Year of publication
Document Type
- Article (18)
- Monograph/Edited Volume (1)
- Habilitation Thesis (1)
- Other (1)
Is part of the Bibliography
- yes (21)
Keywords
- formal languages (3)
- Automata systems (2)
- Lindenmayer systems (2)
- cooperating systems (2)
- 2-tag system (1)
- Accepting Grammars (1)
- Akzeptierende Grammatiken (1)
- Computing with DNA (1)
- Controlled Derivations (1)
- DNA hairpin formation (1)
- Decidability (1)
- Finite automata (1)
- Gesteuerte Ableitungen (1)
- Grammar Systems (1)
- Grammatiksysteme (1)
- Hairpin completions (1)
- Hairpin reductions (1)
- L systems (1)
- LBA problem (1)
- Leftmost Derivations (1)
- Linksableitungen (1)
- Multiple interpretation scheme (1)
- Operation problem (1)
- Parsing (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
A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.