English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-3F37-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-5600-7
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Jeż, Artur1, Author           
Okhotin, Alexander2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 20132013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: Other: Local-ID: BA41F25B8ECBF249C1257C67004F96D7-Jez2013DLT
DOI: 10.1007/978-3-642-38771-5_25
BibTex Citekey: Jez2013DLT
 Degree: -

Event

show
hide
Title: 17th International Conference on Developments in Language Theory
Place of Event: Marne-la-Vallée, France
Start-/End Date: 2013-06-18 - 2013-06-21

Legal Case

show

Project information

show

Source 1

show
hide
Title: Developments in Language Theory
  Abbreviation : DLT 2013
  Subtitle : 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings
Source Genre: Proceedings
 Creator(s):
Beal, Marie-Pierre1, Editor
Carton, Olivier1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 277 - 288 Identifier: ISBN: 978-3-642-38770-8

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 7907 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743