Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Descriptional Complexity of Limited Propagating Lindenmayer Systems
219
0
0.0
(
0
)
Added by
EPTCS
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Authors
Bianca Truthe
Ask ChatGPT about the research
No Arabic abstract
We investigate the descriptional complexity of limited propagating Lindenmayer systems and their deterministic and tabled variants with respect to the number of rules and the number of symbols. We determine the decrease of complexity when the generative capacity is increased. For incomparable families, we give languages that can be described more efficiently in either of these families than in the other.
rate research
Read More
50 -
Laurette Marais (Department of Computer Science
, Stellenboschn University
, Meraka Institute
2017
Previously, self-verifying symmetric difference automata were defined and a tight bound of 2^n-1-1 was shown for state complexity in the unary case. We now consider the non-unary case and show that, for every n at least 2, there is a regular language L_n accepted by a non-unary self-verifying symmetric difference nondeterministic automaton with n states, such that its equivalent minimal deterministic finite automaton has 2^n-1 states. Also, given any SV-XNFA with n states, it is possible, up to isomorphism, to find at most another |GL(n,Z_2)|-1 equivalent SV-XNFA.
We answer two open questions by (Gruber, Holzer, Kutrib, 2009) on the state-complexity of representing sub- or superword closures of context-free grammars (CFGs): (1) We prove a (tight) upper bound of $2^{mathcal{O}(n)}$ on the size of nondeterministic finite automata (NFAs) representing the subword closure of a CFG of size $n$. (2) We present a family of CFGs for which the minimal deterministic finite automata representing their subword closure matches the upper-bound of $2^{2^{mathcal{O}(n)}}$ following from (1). Furthermore, we prove that the inequivalence problem for NFAs representing sub- or superword-closed languages is only NP-complete as opposed to PSPACE-complete for general NFAs. Finally, we extend our results into an approximation method to attack inequivalence problems for CFGs.
A didactical survey of the foundations of Algorithmic Information Theory. These notes are short on motivation, history and background but introduce some of the main techniques and concepts of the field. The manuscript has been evolving over the years. Please, look at Version history below to see what has changed when.
We revisit the complexity of procedures on SFAs (such as intersection, emptiness, etc.) and analyze them according to the measures we find suitable for symbolic automata: the number of states, the maximal number of transitions exiting a state, and the size of the most complex transition predicate. We pay attention to the special forms of SFAs: {normalized SFAs} and {neat SFAs}, as well as to SFAs over a {monotonic} effective Boolean algebra.
Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata cite{Amb98,Amb09,AmYa11,Ber05,Fre09,Mer00,Mer01,Mer02,Yak10,ZhgQiu112,Zhg12}. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum automata with very little quantumness (so-called semi-quantum one- and two-way automata with one qubit memory only); (b) differences, even comparing with probabilistic classical automata, are bigger than expected; (c) a trade-off between the number of classical and quantum basis states needed is demonstrated in one case and (d) languages (or the promise problem) used to show main results are very simple and often explored ones in automata theory or in communication complexity, with seemingly little structure that could be utilized.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
