Results 1 to 10 of about 242 (42)
Tree generating context-free grammars and regular tree grammars are equivalent [PDF]
, 2022 We show that it is decidable whether the language generated by a given context-free grammar over a tree alphabet is a tree language. Furthermore, if the answer to this question is “yes”, then we can even effectively construct a regular tree grammar which
Kószó, Dávid
core +4 more sources
Deciding minimal distinguishing DFAs is NP-complete [PDF]
, 2023 In this paper, we present a proof of the NP-completeness of computing the smallest Deterministic Finite Automaton (DFA) that distinguishes two given regular languages as DFAs.
Martens, Jan
core +2 more sources
A Fibrational Approach to Automata Theory [PDF]
, 2015 For predual categories C and D we establish isomorphisms between opfibrations representing local varieties of languages in C, local pseudovarieties of D-monoids, and finitely generated profinite D-monoids.
Chen, Liang-Ting, Urbat, Henning
core +2 more sources
Groups whose word problems are not semilinear [PDF]
, 2018 Suppose that G is a finitely generated group and W is the formal language of words defining the identity in G. We prove that if G is a nilpotent group, the fundamental group of a finite volume hyperbolic three-manifold, or a right-angled Artin group ...
Gilman, Robert H. +2 more
core +2 more sources
From Finite Automata to Regular Expressions and Back--A Summary on Descriptional Complexity
, 2014 The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower
Gruber, Hermann, Holzer, Markus
core +4 more sources
A B\"uchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
, 2020 We introduce MSO graph storage types, and call a storage type MSO-expressible if it is isomorphic to some MSO graph storage type. An MSO graph storage type has MSO-definable sets of graphs as storage configurations and as storage transformations.
Engelfriet, Joost, Vogler, Heiko
core +1 more source
Minimization, characterizations, and nondeterminism for biautomata [PDF]
, 2013 We show how to minimize biautomata with a Brzozowski-like algorithm by applying reversal and powerset construction twice. Biautomata were recently introduced in [O. Klíma, L. Polák: On biautomata. RAIROTheor. Inf. Appl., 46(4), 2012] as a generalization
Holzer, Markus, Jakobi, Sebastian
core +1 more source
Monoid automata for displacement context-free languages
, 2014 In 2007 Kambites presented an algebraic interpretation of Chomsky-Schutzenberger theorem for context-free languages. We give an interpretation of the corresponding theorem for the class of displacement context-free languages which are equivalent to well ...
A. Sorokin +9 more
core +1 more source
Convex Language Semantics for Nondeterministic Probabilistic Automata [PDF]
, 2018 We explore language semantics for automata combining probabilistic and nondeterministic behaviors. We first show that there are precisely two natural semantics for probabilistic automata with nondeterminism.
Hsu, J. +3 more
core +3 more sources
Tree Transducers and Formal Methods (Dagstuhl Seminar 13192) [PDF]
, 2013 The aim of this Dagstuhl Seminar was to bring together researchers from various research areas related to the theory and application of tree transducers.
Maneth, Sebastian, Seidl, Helmut
core +1 more source