PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Powiadomienia systemowe
  • Sesja wygasła!

Znaleziono wyników: 17

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available A reduction of finitely expandable deep pushdown automata
Dvořáková L., Meduna A.
Schedae Informaticae
|
2017
|
Vol. 26
61--68
EN
For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the present paper demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols—$ and #, where # always appears solely as the pushdown bottom. The paper demonstrates an infinite hierarchy of language families that follows from this main result. The paper also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages. In its conclusion, the paper suggests open problems and topics for the future investigation.
2
Content available Ordered Pure Multi-Pushdown Automata
Meduna A., Soukup O., Zemek P.
Theoretical and Applied Informatics
|
2015
|
Vol. 27, No. 1
25--47
EN
In the presented paper we discuss pure versions of pushdown automata that have no extra non-input symbols. More specifically, we study pure multi-pushdown automata, which have several pushdown lists. We restrict these automata by the total orders defined over their pushdowns or alphabets and determine the accepting power of the automata restricted in this way. Moreover, we explain the significance of the achieved results and relate them to some other results in the automata theory.
3
Content available remote On State-Synchronized Automata Systems
Meduna A., Kučera J.
Schedae Informaticae
|
2015
|
Vol. 24
221--237
EN
In this paper, we introduce a new kind of automata systems, called state-synchronized automata systems of degree n. In general, they consists of n pushdown automata, referred to as their components. These systems can perform a computation step provided that the concatenation of the current states of all their components belongs to a prescribed control language. As its main result, the paper demonstrates that these systems characterize the family of recursively enumerable languages. In fact, this characterization is demostrated in both deterministic and nondeterministic versions of these systems. Restricting their components, these systems provides less computational power.
4
Content available remote On Normal Forms and Erasing Rules in Path Controlled Grammars
Koutnŷ J., Meduna A.
Schedae Informaticae
|
2013
|
Vol. 22
9--18
EN
This paper discusses path controlled grammars { context-free gram- mars with a root-to-leaf path in their derivation trees restricted by a control language. First, it investigates the impact of erasing rules on the generative power of path controlled grammars. Then, it establishes two Chomsky-like normal forms for path controlled grammars - the first allows unit rules, the second allows just one erasing rule.
5
Content available remote New Grammar Systems and Their Application Perspectives
Horáček P., Meduna A.
Schedae Informaticae
|
2013
|
Vol. 22
47--68
EN
This paper presents new grammar systems that describe transfor- mations of syntactic structures. They represent two approaches: synchronous grammars and transducers. The systems consist of well-known models such as context-free grammars and finite automata. Particular attention is paid to synchronization of regulated grammars. The paper recalls formal definitions of the systems and discusses theoretical results regarding their generative and accepting power. The last part briefly introduces application perspectives in natural language translation, illustrated by examples of Czech-English trans- lation.
6
Content available remote Left Random Context ET0L Grammars
Meduna A., Zemek P.
Fundamenta Informaticae
|
2013
|
Vol. 123, nr 3
289--304
EN
Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.
7
Content available Synchronous versions of regulated grammars : generative power and linguistic applications
Horáček P., Meduna A.
Theoretical and Applied Informatics
|
2012
|
Vol. 24, No. 3
175-190
EN
This paper introduces the notion of new synchronous grammars as systems consisting of two context-free grammars with linked rules instead of linked nonterminals. Further, synchronous versions of regulated grammars, specifically, matrix grammars and scattered context grammars, are discussed. From a theoretical point of view, this paper discusses the power of these synchronous grammars. It demonstrates the following main results. First, if we synchronize context-free grammars by linking rules, the grammar generates the languages defined by matrix grammars. Second, if we synchronize matrix grammars by linking matrices, the generative power remains unchanged. Third, synchronous scattered context grammars generate the class of recursively enumerable languages. From a more practical viewpoint, this paper presents linguistic application prospects. The focus is on natural language translation between Japanese and English.
8
Content available Scattered context grammars generating sentences followed by derivation tree
Meduna A., Židek S.
Theoretical and Applied Informatics
|
2011
|
Vol. 23, No. 2
97-106
EN
Propagating scattered context grammars are used to generate sentences of languages defined by scatterd context grammars followed by the strings corresponding to the derivation trees. It is proved that for every language defined by a scattered context grammar, there exists a propagating scattered context grammar whose language consists of original language sentences followed by strings representing their derivation trees.
9
Content available Parsing based on n-path tree - controlled grammars
Čermák M., Koutný J., Meduna A.
Theoretical and Applied Informatics
|
2011
|
Vol. 23, No. 3-4
213-228
EN
This paper discusses recently introduced kind of linguistically motivated restriction placed on tree-controlled grammars-context-free grammars with some root-to-leaf paths in their derivation trees restricted by a control language. We deal with restrictions placed on n greater-than or equal to 1 paths controlled by a deterministic context-free language, and we recall several basic properties of such a rewriting system. Then, we study the possibilities of corresponding parsing methods working in polynomial time and demonstrate that some non-context-free languages can be generated by this regulated rewriting model. Furthermore, we illustrate the syntax analysis of LL grammars with controlled paths. Finally, we briefly discuss how to base parsing methods on bottom-up syntax-analysis.
10
Content available remote Some power - decreasing derivation restrictions in grammar systems
Meduna A., Čermák M., Masopust T.
Schedae Informaticae
|
2010
|
Vol. 19
23-34
EN
In this paper, we place some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by the regular languages. The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for some k greather than 1. The second restriction says how many blocks of non-terminals can be in each sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in each sentential form. We demonstrate that under these restrictions, the grammar systems generate different families of languages. Irideed, under the first restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enu-merable languages. In the end, the family of languages generated by grammar systems under the third restriction is equal to the family of languages generated by programmed grammars with context-free rules without e-rules of finite index.
11
Content available remote On Descriptional Complexity of Partially Parallel Grammars
Masopust T., Meduna A.
Fundamenta Informaticae
|
2008
|
Vol. 87, nr 3-4
407-415
EN
This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more than two selectors.
12
Content available remote Context-Free and E0L Derivations over Free Groups
Meduna A., Bildo R., Blatny' P.
Schedae Informaticae
|
2007
|
Vol. 16
9-20
EN
In the context-free and E0L grammars discussed in this pa- per, the derivations are introduced over free groups rather than free monoids. It is proved that both grammars with derivations introduced in this way characterize the family of recursively enumerable languages in a very succinct way. Specifically, this characterization is based on the eight-nonterminal context-free grammars and six-nonterminal E0L grammars over free groups.
13
Content available remote Multigenerative Grammar Systems
Meduna A., Lukas R.
Schedae Informaticae
|
2006
|
Vol. 15
175-188
EN
This paper presents new models for all recursive enumerable languages. These models are based on multigenerative grammar systems that simultaneously generate several strings in a parallel way. The components of these models are context -free grammars, working in a leftmost way. The rewritten nonterminals are determined by a finite set of nonterminal sequences.
14
Content available remote New Language Operations in Formal Language Theory
Meduna A., Vítek M.
Schedae Informaticae
|
2004
|
Vol. 13
123-150
EN
Stringology represents a modern part of the formal language theory which deal with strings, languages and operations on them. It introduces many new languages operations, which can be divided into two groups - insertion and deletion operations. Some of these operations are described in [1] . This paper presents these operations and some of their properties. Especially, closure properties are studied here. New algorithms that construct finite automata accepting languages resulting from some of these operations are described here. We actually demonstrate by designing these algorithms, that the family of regular languages is closed under these operations.
15
Content available remote One-Turn Regulated Pushdown Automata and Their Reduction
Meduna A., Kolar D.
Fundamenta Informaticae
|
2002
|
Vol. 51, nr 4
399-405
EN
This paper discusses some simple and natural restrictions of regulated pushdown automata, whose moves are regulated by some control languages. Most importantly, it studies one-turn regulated pushdown automata and proves that they characterize the family of recursively enumerable languages. In fact, this characterization holds even for atomic one-turn regulated pushdown automata of a reduced size. This result is established in terms of acceptance by final state and empty pushdown, acceptance by final state, and acceptance by empty pushdown.
16
Content available remote Uniform Generation of languages by scattered context grammars
Meduna A.
Fundamenta Informaticae
|
2001
|
Vol. 45, nr 3
231-235
EN
The present paper discusses the uniform generation of languages by scattered context grammars. More specifically, it demonstrates that every recursively enumerable language can be generated by a scattered context grammar, G, so that every sentential form in a generation of a sentence has the form y1Ľym u, where u is a terminal word and each yi is a permutation of either of two equally long words, z1 E {A, B,C}* and z2 E {A, B, D}*, where A, B, C, and D are G's nonterminals. Then, it presents an analogical result so that u precedes y1...ym.
17
Content available remote Multisequential Grammars with Homogeneous Selectors
Meduna A., Vurm P.
Fundamenta Informaticae
|
2001
|
Vol. 48, nr 1
55-60
EN
This paper deals with selective substitution grammars. It concentrates on multisequential grammars with homogeneous selectors that have all their activated parts identical. The present paper reduces the number and size of selectors in these grammars. Indeed, it demonstrates that for every phrase-structure grammar, there exists an equivalent multisequential grammar having two homogeneous selectors, either of which has only two activated parts.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.