All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Algebraic methods in automata and formal language theory

Project goals

The project is aimed to develop algebraic methods in formal language theory. In particular, we will further investigate classes of syntactic structures of regular languages like (ordered) syntactic monoids, syntactic semirings, syntactic homomorphisms, syntactic semirings with the image of the language, etc. with the goal of effectively characterizing membership to important classes of languages. We will also consider the graph structures of the canonical automata. We are going to continue our study ofimplicit language equations. We will mainly concentrate on finding some common factors of different results ensuring regularity of solutions with the aim of formulating a unified theory. We will attempt to develop algorithms for calculating maximal solutions in those cases where they are regular. We will also deal with generalizations of the classical languages of finite words to the so-called tree languages, languages of infinite words and trace languages. Within the project we are going to

Keywords

automataregular languagesvarietiessemiringsinfinite wordstraces

Public support

  • Provider

    Czech Science Foundation

  • Programme

    Standard projects

  • Call for proposals

    Standardní projekty 9 (SGA02006GA-ST)

  • Main participants

  • Contest type

    VS - Public tender

  • Contract ID

    201/06/0936

Alternative language

  • Project name in Czech

    Algebraické metody v teorii automatů a formálních jazyků

  • Annotation in Czech

    Projekt je zaměřen na rozvoj algebraických metod v teorii formálních jazyků. Zejména budeme dále zkoumat třídy syntaktických struktur regulárních jazyků, jako (uspořádaných) syntaktických monoidů, syntaktických polookruhů, syntaktických homomorfismů, syntaktických polookruhů s obrazem jazyka, atd. s cílem efektivní charakterizace příslušnosti k důležitým třídám jazyků. Budeme též uvažovat grafovou strukturu kanonických automatů. Chystáme se pokračovat v našem studiu implicitních jazykových rovnic. Hlavně se zaměříme na hledání společných rysů různorodých výsledků zajišťujících regularitu řešení s cílem formulace jednotné teorie. Budeme se též věnovat návrhům algoritmů pro výpočet maximálních řešení v těch případech, kdy jsou tato regulární. Též sebudeme zabývat zobecněními klasických jazyků konečných slov na takzvané stromové jazyky, jazyky nekonečných slov a jazyky stop. V rámci projektu budeme pokračovat v naší široké mezinárodní spolupráci. Výsledky budou prezentovány na prestižních

Scientific branches

  • R&D category

    ZV - Basic research

  • CEP classification - main branch

    BA - General mathematics

  • CEP - secondary branch

    IN - Informatics

  • CEP - another secondary branch

  • 10101 - Pure mathematics
    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Completed project evaluation

  • Provider evaluation

    U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

  • Project results evaluation

    Our research has concentrated on several areas of theory of formal languages. According to the plan, we have studied syntactic structures of languages, and obtained new results about some important classes of regular languages. We have characterized seve

Solution timeline

  • Realization period - beginning

    Jan 1, 2006

  • Realization period - end

    Dec 31, 2008

  • Project status

    U - Finished project

  • Latest support payment

    Apr 25, 2008

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

    CEP09-GA0-GA-U/02:2

  • Data delivery date

    Oct 22, 2009

Finance

  • Total approved costs

    900 thou. CZK

  • Public financial support

    900 thou. CZK

  • Other public sources

    0 thou. CZK

  • Non public and foreign sources

    0 thou. CZK

Basic information

Recognised costs

900 CZK thou.

Public support

900 CZK thou.

100%


Provider

Czech Science Foundation

CEP

BA - General mathematics

Solution period

01. 01. 2006 - 31. 12. 2008