Zobrazeno 1 - 10
of 289
pro vyhledávání: '"03D05"'
Autor:
Droste, Manfred, Vogler, Heiko
We consider weighted automata over words and over trees where the weight algebras are strong bimonoids, i.e., semirings which may lack distributivity. It is well known that, for each such weighted automaton, its run semantics and its initial algebra
Externí odkaz:
http://arxiv.org/abs/2409.08727
Autor:
Lopez, Aliaume
A fundamental construction in formal language theory is the Myhill-Nerode congruence on words, whose finitedness characterizes regular language. This construction was generalized to functions from $\Sigma^*$ to $\mathbb{Z}$ by Colcombet, Dou\'eneau-T
Externí odkaz:
http://arxiv.org/abs/2409.07882
We explore the idea of using automatic and similar kind of presentations of structures to deal with the conceptual problem of natural proof-theoretic ordinal notations. We conclude that this approach still does not meet the goals.
Comment: 19 pa
Comment: 19 pa
Externí odkaz:
http://arxiv.org/abs/2407.10198
We consider the images of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings). These images are subsets of the carrier set of the underlying strong bimonoid. We consider locally finite, weakly loc
Externí odkaz:
http://arxiv.org/abs/2405.20753
Autor:
Knapik, Teodor
Combinatorial generation of expander families and Lindenmayer-style development models are both parallel in nature. Both can be handled within proposed parallel graph grammar formalism. Their first-order properties can then be checked by encompassing
Externí odkaz:
http://arxiv.org/abs/2405.17629
A new family of categorial grammars is proposed, defined by enriching basic categorial grammars with a conjunction operation. It is proved that the formalism obtained in this way has the same expressive power as conjunctive grammars, that is, context
Externí odkaz:
http://arxiv.org/abs/2405.16662
Autor:
Lopez, Aliaume
We are interested in characterizing which classes of finite graphs are well-quasi-ordered by the induced subgraph relation. To that end, we devise an algorithm to decide whether a class of finite graphs well-quasi-ordered by the induced subgraph rela
Externí odkaz:
http://arxiv.org/abs/2405.10894
Autor:
Levine, Alex
We study subsets $E$ of finitely generated groups where the set of all words over a given finite generating set that lie in $E$ forms a context-free language. We call these sets recognisably context-free. They are invariant of the choice of generatin
Externí odkaz:
http://arxiv.org/abs/2312.04191
Autor:
Bell, Jason, Gorman, Alexi Block
This paper concerns the expansion of the real ordered additive group by a predicate for a subset of $[0,1]$ whose base-$r$ representations are recognized by a B\"uchi automaton. In the case that this predicate is closed, a dichotomy is established fo
Externí odkaz:
http://arxiv.org/abs/2311.11162
In this paper we study the satisfiability and solutions of group equations when combinatorial, algebraic and language-theoretic constraints are imposed on the solutions. We show that the solutions to equations with length, lexicographic order, abelia
Externí odkaz:
http://arxiv.org/abs/2309.00475