Zobrazeno 1 - 10
of 95
pro vyhledávání: '"Sebastian Jakobi"'
Autor:
Markus Holzer, Sebastian Jakobi
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 151, Iss Proc. AFL 2014, Pp 271-285 (2014)
We study structural restrictions on biautomata such as, e.g., acyclicity, permutation-freeness, strongly permutation-freeness, and orderability, to mention a few. We compare the obtained language families with those induced by deterministic finite au
Externí odkaz:
https://doaj.org/article/d0ec80a6fa0f4e89bd3955773e44368e
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 31, Iss Proc. DCFS 2010, Pp 110-119 (2010)
We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has alpha states, for all n and alpha satisfyi
Externí odkaz:
https://doaj.org/article/b77da2bdaff547fd97512e12a254a339
Autor:
Markus Holzer, Sebastian Jakobi
Publikováno v:
Information and Computation. 259:225-236
We study the computational complexity of problems related to distinguishability sets for regular languages. Roughly speaking, the distinguishability set \(\mathsf {D}(L)\) for a (not necessarily regular) language \(L\) consists of all words \(w\) tha
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fd6e9ac1a5b08245a3ef519c186cbcc0
https://doi.org/10.1016/j.ic.2017.09.003
https://doi.org/10.1016/j.ic.2017.09.003
Publikováno v:
International Journal of Foundations of Computer Science. 29:251-270
We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characte
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::719ec7b0c484ff8aafa86c83bdff0601
https://doi.org/10.1142/s0129054118400063
https://doi.org/10.1142/s0129054118400063
Publikováno v:
Fundamenta Informaticae. 155:89-110
We investigate the state complexity of the cut and iterated cut operation for determin- istic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expr ...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::515a2c6336ff47a4b2ef5706c8152be5
https://doi.org/10.3233/fi-2017-1577
https://doi.org/10.3233/fi-2017-1577
Publikováno v:
Theoretical Computer Science. 682:122-137
We investigate chop operations, which can be seen as generalized concatenation. For several language families of the Chomsky hierarchy we prove (non)closure properties under chop operations and incomparability to the family of languages that are the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3a03e6ee5e0d9dc8e81826dd3ff93956
https://doi.org/10.1016/j.tcs.2017.02.002
https://doi.org/10.1016/j.tcs.2017.02.002
Publikováno v:
Theoretical Computer Science. 679:18-30
Finite languages are an important sub-regular language family, which were intensively studied during the last two decades in particular from a descriptional complexity perspective. An important contribution to the theory of finite languages are the d
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e3e5e24f76e7157f32056acb3bfe9bf6
https://doi.org/10.1016/j.tcs.2016.10.006
https://doi.org/10.1016/j.tcs.2016.10.006
Publikováno v:
Fundamenta Informaticae. 148:267-289
We consider computational complexity of problems related to partial word au- tomata. Roughly speaking, a partial word is a word in which some positions are unspecified, and a partial word automaton is a finite automaton that accepts a partial word la
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::35a94dd4cf9c9e615b3aabe0555d11ec
https://doi.org/10.3233/fi-2016-1435
https://doi.org/10.3233/fi-2016-1435
Autor:
Markus Holzer, Sebastian Jakobi
Publikováno v:
International Journal of Foundations of Computer Science. 27:161-185
We compare deterministic finite automata (DFAs) and biautomata under the following two aspects: structural similarities between minimal and hyper-minimal automata, and computational complexity of the minimization and hyper-minimization problem. Conce
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::153f9894ffa784fb6d7f9fc107c01524
https://doi.org/10.1142/s0129054116400050
https://doi.org/10.1142/s0129054116400050
Autor:
Sebastian Jakobi, Markus Holzer
Publikováno v:
Theoretical Computer Science. 610:59-77
We investigate the descriptional and computational complexity of boundary sets of regular and context-free languages. For a letter a, the right (left, respectively) a-boundary set of a language L consists of the words in L whose a-predecessor or a-su
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e50e0d1481e1dd6865cd4e336f7da6cc
https://doi.org/10.1016/j.tcs.2015.07.032
https://doi.org/10.1016/j.tcs.2015.07.032