We show the existence of rational trace languages defined over direct products of free monoids that have inherent ambiguity of the order of log n and n 1/2 . This result is obtained by studying the relationship between trace languages and linear context-free grammars that satisfy a special unambiguity condition on the position of the last step of derivation.
Unambiguous Turn Position and Rational Trace Languages / M. Goldwurm, K. Wich. - [s.l] : Universitaet Stuttgart, 2005.
Unambiguous Turn Position and Rational Trace Languages
M. Goldwurm;
2005
Abstract
We show the existence of rational trace languages defined over direct products of free monoids that have inherent ambiguity of the order of log n and n 1/2 . This result is obtained by studying the relationship between trace languages and linear context-free grammars that satisfy a special unambiguity condition on the position of the last step of derivation.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
newklaus.pdf
accesso aperto
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
309.95 kB
Formato
Adobe PDF
|
309.95 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
