Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor

Author(s):

Jez, Artur
Okhotin, Alexander
dblp
dblp
Not MPG Author(s):

Okhotin, Alexander

Editor(s):

Beal, Marie-Pierre
Carton, Olivier
dblp
dblp
Not MPII Editor(s):

Beal, Marie-Pierre
Carton, Olivier

BibTeX cite key*:

Jez2013DLT

Title, Booktitle

Title*:

Unambiguous Conjunctive Grammars over a One-Letter Alphabet

Booktitle*:

17th International Conference on Developments in Language Theory (DLT 2013)

Event, URLs

URL of the conference:

http://dlt2013.sciencesconf.org/

URL for downloading the paper:

http://dx.doi.org/10.1007/978-3-642-38771-5_25

Event Address*:

Marne-la-Vallée, France
Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

18 June 2013
Event End Date:

21 June 2013

Publisher

Name*:

Springer

URL:

http://link.springer.com/

Address*:

Heidelberg, Germany
Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

7907
Number:


Month:


Pages:

277-288

Year*:

2013
VG Wort Pages:


ISBN/ISSN:

978-3-642-38770-8
Sequence Number:


DOI:

10.1007/978-3-642-38771-5_25


Note, Abstract, ©


(LaTeX) Abstract:

It is demonstrated that unambiguous conjunctive grammars
over a unary alphabet $\Sigma=\{a\}$ have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base $k \geqslant 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.

Keywords:

Conjunctive grammars, Ambiguity, Language equations, Undecidability, Unary languages



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Jez2013DLT,
AUTHOR = {Jez, Artur and Okhotin, Alexander},
 EDITOR = {Beal, Marie-Pierre and Carton, Olivier},
 TITLE = {Unambiguous Conjunctive Grammars over a One-Letter Alphabet},
 BOOKTITLE = {17th International Conference on Developments in Language Theory (DLT 2013)},
 PUBLISHER = {Springer},
 YEAR = {2013},
 VOLUME = {7907},
 PAGES = {277--288},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Marne-la-Vallée, France},
 ISBN = {978-3-642-38770-8},
 DOI = {10.1007/978-3-642-38771-5_25},
}

Entry last modified by Artur Jez, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
01/21/2014 03:29:19 PM
Revision
0.



Editor
Artur Jez



Edit Date
01/21/2014 03:29:19 PM