Detail publikace

How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars

HAVEL, M.; KŘIVKA, Z.; MEDUNA, A. How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars. In Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications. Electronic Proceedings in Theoretical Computer Science, EPTCS. Göttingen: School of Computer Science and Engineering, University of New South Wales, 2024. p. 86-99. ISSN: 2075-2180.
Název česky
Jak dokázat metalinearitu a regulárnost pomocí stromově omezených obecných gramatik
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Havel Martin, Ing. (UIFS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
Klíčová slova

stromově-omezené gramatiky, regulované gramatiky, metalineární gramatiky,
k-lineární gramatiky, regulární gramatiky, kontextová závislost, generativní
síla

Abstrakt

Příspěvek představuje derivační stromy obecných gramatik. V těchto stromek
definuje páry kontextové závislých uzlů, které odpovídají přepisu dvou sousedních
symbolů pomocí nebezkontextového pravidla. Článek dokazuje jazyky generované
obecnými gramatikami s lineárním jádrem a s pomalu větvícím derivačním stromem
jsou k-lineární, existuje-li konstanta u taková, že každá věta w v generovaném
jazyce tvoří poslední patro derivačního stromu, kde žádná sousední cesta nemá
více jak u kontextově-závislých uzlů. Příspěvek vysvětluje výsledek jako nástroj
pro demonstraci, že je nějaký jazyk k-lineární či regulární.

Rok
2024
Strany
86–99
Časopis
Electronic Proceedings in Theoretical Computer Science, EPTCS, roč. 407, č. 09, ISSN 2075-2180
Sborník
Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications
Konference
14th International Workshop on Non-Classical Models of Automata and Applications, Göttingen, Germany, DE
Vydavatel
School of Computer Science and Engineering, University of New South Wales
Místo
Göttingen
DOI
10.4204/EPTCS.407.7
EID Scopus
2-s2.0-85205004625
BibTeX 
@inproceedings{BUT189042,
  author="Martin {Havel} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars",
  booktitle="Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications",
  year="2024",
  journal="Electronic Proceedings in Theoretical Computer Science, EPTCS",
  volume="407",
  number="09",
  pages="86--99",
  publisher="School of Computer Science and Engineering, University of New South Wales",
  address="Göttingen",
  doi="10.4204/EPTCS.407.7",
  issn="2075-2180",
  url="https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?NCMA2024:3"
}
Soubory
Nahoru