Context-free languages and pushdown automata
Public support
Provider
Ministry of Education, Youth and Sports
Programme
KONTAKT
Call for proposals
—
Main participants
—
Contest type
M2 - International cooperation
Contract ID
5364/2010-32
Alternative language
Project name in Czech
Bezkontextové gramatiky a zásobníkové automaty
Annotation in Czech
Plánovaný výzkum se zaměří na studium bezkontextových jazyků a zásobníkových automatů a jejich aplikací. Pro hlubší pochopení struktur formálních jazyků je nápomocné studovat jejich kombinatorické vlastnosti. Jedním z předmětů výzkumu je problém primitivních slov. Slovo nazýváme primitivní, pokud není mocninou jiného slova. P. Dömösi, M. Ito a S. Horváth prezentovali domněnku, že jazyk všech primitivních slov nad abecedou s několika symboly, Q, není bezkontextový. Nedávno publikované články se stále zabývají tímto proslulým dohadem, který je stále otevřeným problémem. Plánujeme dále rozvíjet toto zkoumání se zaměřením na malé bezkontextové gramatiky generující primitivní slova. Na druhou stranu, vezmeme-li v úvahu, že homomorfický obraz neprimitivníhoslova je také neprimitivní, budeme také studovat, zda je Q skutečnou homomorfickou charakterizací Chomsky-Schützenberger-Stanleyho typu. Doufáme, že toto zkoumání povede na důkaz platnosti či neplatnosti předchozí domněnky a otevřeného problému. Dále by
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
JC - Computer hardware and software
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)<br>20206 - Computer hardware and architecture
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
We accomplished the main project goal to study context-free grammars and automata. The original results about their properties were presented at 4 public seminars and published in 4 international journals and several conferences.
Solution timeline
Realization period - beginning
Jan 1, 2010
Realization period - end
Dec 31, 2011
Project status
U - Finished project
Latest support payment
Mar 7, 2011
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP12-MSM-ME-U/01:1
Data delivery date
Jul 12, 2012
Finance
Total approved costs
124 thou. CZK
Public financial support
124 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK