Search

Start Over Creator Meduna, Alexander

1. Automata with two-sided pushdowns defined over free groups generated by reduced alphabets

Creator:
Blatný, Petr, Bidlo, Radek, and Meduna, Alexander
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
pushdown automata, modifications, and recursively enumerable languages
Language:
English
Description:
This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by no more than four symbols.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

2. Multi-island finite automata and their even computation

Creator:
Kolář, Dušan, Meduna, Alexander, and Tomko, Martin
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
finite automata, graph-based decomposition, regulated computation, and infinite hierarchies of language families
Language:
English
Description:
This paper discusses n-island finite automata whose transition graphs can be expressed as n-member sequences of islands i1,i2,…,in, where there is a bridge leaving ij and entering ij+1 for each 1≤j≤n−1. It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that n-island finite automata and Rosebrugh-Wood n-parallel right-linear grammars are equivalent. Then, making use of this main result, it demonstrates that under this assumption, the language family defined by n-island finite automata is properly contained in that defined by (n+1)-island finite automata for all n≥1. The paper also points out that this infinite hierarchy occurs between the family of regular languages and that of context-sensitive languages. Open questions are formulated in the conclusion.
Rights:
http://creativecommons.org/licenses/by-nc-sa/4.0/ and policy:public

3. Multigenerative grammar systems and matrix grammars

Creator:
Lukáš, Roman and Meduna, Alexander
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
multigenerative grammar systems, simultaneously controlled derivations, and matrix grammars
Language:
English
Description:
Multigenerative grammar systems are based on cooperating context-free grammatical components that simultaneously generate their strings in a rule-controlled or nonterminal-controlled rewriting way, and after this simultaneous generation is completed, all the generated terminal strings are combined together by some common string operations, such as concatenation, and placed into the generated languages of these systems. The present paper proves that these systems are equivalent with the matrix grammars. In addition, we demonstrate that these systems with any number of grammatical components can be transformed to equivalent two-component versions of these systems. The paper points out that if these systems work in the leftmost rewriting way, they are more powerful than the systems working in a general way.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

4. Tree-controlled grammars with restrictions placed upon cuts and paths

Creator:
Koutný, Jiří and Meduna, Alexander
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
context-free grammars, tree-controlled grammars, restricted derivation trees, paths, cuts, and language families
Language:
English
Description:
First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively enumerable languages. In addition, it places a binary-relation-based restriction upon these grammars and demonstrate that this additional restriction does not affect the generative power of these grammars.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public