_:N60155fd963b94f7885c42c433336d044 .
.
.
"language equations" .
"recursive functions" .
.
"decision problem" .
"function" .
.
"Computation Theory and Mathematics" .
_:Neb0dfb2a23144f6b89c026f899c13ada _:N44dbf5b65c184e8bbe56540818492770 .
"paper" .
"automata" .
_:Naf8f5dcfdf954045bbc0dc4e61f3c347 "doi" .
_:Nc07eefcb84654f06b35839a9c72d1381 .
.
"problem" .
"https://scigraph.springernature.com/explorer/license/" .
.
"large class" .
.
_:N44dbf5b65c184e8bbe56540818492770 .
"2008-08-21" .
_:N8c74f6c04c1b4864a97430950020600f "1" .
.
"essential step" .
.
"undecidability" .
"cellular automata" .
.
.
.
.
_:N60155fd963b94f7885c42c433336d044 .
"27" .
.
"Academy of Finland, Helsinki, Finland" .
"Alexander" .
.
"Information and Computing Sciences" .
"Distributed Computing" .
.
.
"Je\u017C" .
"https://doi.org/10.1007/s00224-008-9139-5" .
_:Naf8f5dcfdf954045bbc0dc4e61f3c347 .
.
"Okhotin" .
"It has recently been proved (Je\u017C, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations." .
"2008-08-21" .
_:Naf8f5dcfdf954045bbc0dc4e61f3c347 .
.
"Artur" .
.
.
"unbounded growth" .
.
"equations" .
"Mathematical Sciences" .
"class" .
"unary alphabet" .
_:N60155fd963b94f7885c42c433336d044 "dimensions_id" .
.
"Institute of Computer Science, University of Wroc\u0142aw, Wroc\u0142aw, Poland" .
"1433-0490" .
.
.
.
_:N1809a4fc981d4b38821078f8e418f541 .
.
"Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth" .
"2022-08-04T16:57" .
"conjunctive grammars" .
_:N8c74f6c04c1b4864a97430950020600f .
"present paper" .
"simulations" .
_:Neb0dfb2a23144f6b89c026f899c13ada .
"article" .
.
"unary languages" .
_:N8c74f6c04c1b4864a97430950020600f .
"non-regular languages" .
.
.
_:N1809a4fc981d4b38821078f8e418f541 .
"positional notation" .
.
_:N60155fd963b94f7885c42c433336d044 "pub.1032338044" .
"articles" .
"Department of Mathematics, University of Turku, Turku, Finland" .
"Springer Nature" .
_:Nc07eefcb84654f06b35839a9c72d1381 .
.
"Academy of Finland, Helsinki, Finland" .
.
.
.
"false"^^ .
"Institute of Computer Science, University of Wroc\u0142aw, Wroc\u0142aw, Poland" .
.
"step" .
"argument" .
"1432-4350" .
_:Nc07eefcb84654f06b35839a9c72d1381 "46" .
_:Neb0dfb2a23144f6b89c026f899c13ada .
"Applied Mathematics" .
"grammar" .
.
.
"growth rate" .
_:N1809a4fc981d4b38821078f8e418f541 "Springer Nature - SN SciGraph project" .