Nondeterministic syntactic complexity

DOI10.1007/978-3-030-71995-1_23MaRDI QIDQ2233426zbMATH OpenOpenAlexFDO

Authors Robert S. R. Myers, Stefan Milius, Henning Urbat

Publication date 18 October 2021

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2101.03039

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A (co)algebraic theory of succinct automata
• Adjoint machines, state-behavior machines, and duality
• Antichains: A New Algorithm for Checking Universality of Finite Automata
• Bideterministic automata and minimal representations of regular languages
• Categories of algebraic contexts equivalent to idempotent semirings and domain semirings
• Chrobak normal form revisited, with applications
• Coalgebraic constructions of canonical nondeterministic automata
• Communication complexity method for measuring nondeterminism in finite automata
• Derivatives of Regular Expressions
• Discrete-time machines in closed monoidal categories. I
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Factor theory and the unity of opposites
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Finite automata and unary languages
• Fuzzy machines in a category
• General lattice theory. New appendices with B. A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt, F. Wehrung, R. Wille.
• scientific article; zbMATH DE number 3787631 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• Inference of Reversible Languages
• Mathematical Foundations of Computer Science 2003
• Minimal NFA and biRFSA Languages
• Minimal NFA Problems are Hard
• New Interpretation and Generalization of the Kameda-Weiner Method.
• On continuous nondeterminism and state minimality
• On the State Minimization of Nondeterministic Finite Automata
• On viewing block codes as finite automata.
• Primes, irreducibles and extremal lattices
• Representation theory of finite semigroups over semirings.
• Residual finite state automata
• Syntactic semiring of a language. (Extended abstract)
• The category of semilattices
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• The trellis structure of maximal fixed-cost codes
• Theory of átomata

Cited in

(3)

• scientific article; zbMATH DE number 6606360 (Why is no real title available?)
• Bideterministic weighted automata
• Bideterministic weighted automata

This page was built for publication: Nondeterministic syntactic complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2233426)