Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Unambiguous Conjunctive Grammars over a One-letter Alphabet

Jeż, A., & Okhotin, A. (2013). Unambiguous Conjunctive Grammars over a One-letter Alphabet. In M.-P. Beal, & O. Carton (Eds.), Developments in Language Theory (pp. 277-288). Berlin: Springer. doi:10.1007/978-3-642-38771-5_25.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Jeż, Artur1, Autor           
Okhotin, Alexander2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: It is demonstrated that unambiguous conjunctive grammars over a unary alphabet Σ=a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base k ≥qslant 11 and for every one-way real-time cellular automaton operating over the alphabet of base-k digits \big{\lfloor\frac{k+9}{4}\rfloor, \ldots, \lfloor\frac{k+1}{2}\rfloor\big, the language of all strings a^n with the base-k notation of the form \D1w\D1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L_0, testing whether a given unambiguous conjunctive grammar generates L_0 is undecidable.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20132013
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Anderer: Local-ID: BA41F25B8ECBF249C1257C67004F96D7-Jez2013DLT
DOI: 10.1007/978-3-642-38771-5_25
BibTex Citekey: Jez2013DLT
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 17th International Conference on Developments in Language Theory
Veranstaltungsort: Marne-la-Vallée, France
Start-/Enddatum: 2013-06-18 - 2013-06-21

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Developments in Language Theory
  Kurztitel : DLT 2013
  Untertitel : 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings
Genre der Quelle: Konferenzband
 Urheber:
Beal, Marie-Pierre1, Herausgeber
Carton, Olivier1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 277 - 288 Identifikator: ISBN: 978-3-642-38770-8

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 7907 Artikelnummer: - Start- / Endseite: - Identifikator: ISSN: 0302-9743