Results 11 to 20 of about 307 (62)
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
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
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
The Height of Piecewise-Testable Languages with Applications in Logical Complexity [PDF]
, 2016 The height of a piecewise-testable language L is the maximum length of the words needed to define L by excluding and requiring given subwords. The height of L is an important descriptive complexity measure that has not yet been investigated in a ...
Karandikar, Prateek +1 more
core +1 more source
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
Colored operads, series on colored operads, and combinatorial generating systems [PDF]
, 2019 We introduce bud generating systems, which are used for combinatorial generation. They specify sets of various kinds of combinatorial objects, called languages.
Giraudo, Samuele
core +2 more sources
Advanced Automata Minimization [PDF]
, 2012 We present an efficient algorithm to reduce the size of nondeterministic Buchi word automata, while retaining their language. Additionally, we describe methods to solve PSPACE-complete automata problems like universality, equivalence and inclusion for ...
Abdulla P. +15 more
core +4 more sources
Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata [PDF]
, 2023 A weighted finite automaton has the finite-image property if the image of the weighted language associated with it is finite. We show two undecidability results concerning the finite-image property of weighted finite automata over semirings, respectively
Droste Manfred +2 more
core +1 more source