A counterexample to a conjecture concerning concatenation hierarchies

• Název česky: Protiříklad k hypotéze ohledně konkatenačních hierarchií
• Autoři: KLÍMA Ondřej; ALMEIDA Jorge
• Rok publikování: 2009
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Information Processing Letters
• Fakulta / Pracoviště MU: Přírodovědecká fakulta
• Obor: Obecná matematika
• Klíčová slova: Formal languages; Regular languages; Concatenation hierarchies; Level two; Star-free languages
• Popis: Nalezli jsme protipříklad k hypotéze, kterou zformuloval Straubing v roce 1986 a která se týkala jisté algebraické charakterizace regulárních jazyků stupně 2 v Straubing Thérien hierarchii bezhvězdičkových regulárních jazyků.

Související projekty

• Institut Teoretické Informatiky
• Matematické struktury a jejich fyzikální aplikace
• Algebraické metody v teorii automatů a formálních jazyků II