Zobrazeno 1 - 10
of 13
pro vyhledávání: '"Zuzana Bednárová"'
Publikováno v:
Theoretical Computer Science. 918:105-122
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fd001825fd97283eb8b0ca5efa29adb5
https://doi.org/10.1016/j.tcs.2022.03.024
https://doi.org/10.1016/j.tcs.2022.03.024
Autor:
Viliam Geffert, Zuzana Bednárová
Publikováno v:
Fundamenta Informaticae. 181:99-127
We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n)ɛ. This is required for weak space bounds on the size of their counters, for real-time and one-way, and fo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ab2487c6303c76c1159a9843116af54b
https://doi.org/10.3233/fi-2021-2053
https://doi.org/10.3233/fi-2021-2053
Publikováno v:
Journal of Computer and System Sciences. 90:99-114
We study the size-cost of Boolean operations on constant height nondeterministic pushdown automata, i.e. on pushdown automata with a constant limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the ex
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dd742a2bde0141e4ffd6e93e0ce6b2c5
https://doi.org/10.1016/j.jcss.2017.06.007
https://doi.org/10.1016/j.jcss.2017.06.007
Autor:
Viliam Geffert, Zuzana Bednárová
Publikováno v:
Information and Computation. 253:381-398
We shall consider nondeterministic and deterministic automata equipped with a limited pushdown (constant height npda s and dpda s) as well as their two-way versions (constant height 2 npda s and 2 dpda s). We show two double-exponential gaps for thes
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::42c6dd4fa9a9e2d1c61b6b98c4800b72
https://doi.org/10.1016/j.ic.2016.06.005
https://doi.org/10.1016/j.ic.2016.06.005
Publikováno v:
Developments in Language Theory ISBN: 9783030248857
DLT
DLT
Edit distance \(\ell \)-neighborhood of a language \(\mathcal {L}\) is the set of strings that can be obtained by at most \(\ell \) elementary edit operations—deleting or inserting one symbol in the string—from some string in \(\mathcal {L}\). We
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ed1d20d6027fb2f0db2454929cc91e39
https://doi.org/10.1007/978-3-030-24886-4_8
https://doi.org/10.1007/978-3-030-24886-4_8
Publikováno v:
International Journal of Foundations of Computer Science. 27:259-281
We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak log log n space, (ii) log log n is a tight space lowe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::34f9677c1a2dc748336be48ccd3f9cbd
https://doi.org/10.1142/s0129054116400098
https://doi.org/10.1142/s0129054116400098
Autor:
Zuzana Bednárová, Viliam Geffert
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319924014
MCU
MCU
We show that, for nondeterministic and alternating machines with weak space bounds, the minimal space that is required for accepting a nonregular language by real-time or one-way multicounter automata is \((\log n)^{\varepsilon }\!\). The same space
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::591371252bc7df7320989d56e2061c33
https://doi.org/10.1007/978-3-319-92402-1_6
https://doi.org/10.1007/978-3-319-92402-1_6
Publikováno v:
Information and Computation. 237:257-267
We study the descriptional cost of removing nondeterminism in constant height pushdown automata-i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constan
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fe70f57700ae1b0722221936084aebf4
https://doi.org/10.1016/j.ic.2014.03.002
https://doi.org/10.1016/j.ic.2014.03.002
Autor:
Viliam Geffert, Zuzana Bednárová
Publikováno v:
Language and Automata Theory and Applications ISBN: 9783319049205
LATA
LATA
We shall consider nondeterministic and deterministic automata equipped with a limited pushdown constant height npdas and dpdas as well as their two-way versions constant height 2npdas and 2dpdas.We show two double-exponential gaps for these devices,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::394d000148fe2be2ecfdaf75f56b3b0d
https://doi.org/10.1007/978-3-319-04921-2_9
https://doi.org/10.1007/978-3-319-04921-2_9
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783642385353
CSR
CSR
We study the size-cost of Boolean operations on constant height nondeterministic pushdown automata, i.e. on pushdown automata with a constant limit on the size of the pushdown. For intersection, we show an exponential simulation and prove that the ex
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a308039f3a295dc566c8871dd1532315
https://doi.org/10.1007/978-3-642-38536-0_9
https://doi.org/10.1007/978-3-642-38536-0_9