scientific article; zbMATH DE number 1418342

zbMath0955.68068MaRDI QIDQ4941905

Cyril Nicaud

Publication date: 19 March 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

complexity of a regular language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (23)

The effect of end-markers on counter machines and commutativity ⋮ Some complexity results for polynomial rational expressions. ⋮ Operations on Permutation Automata ⋮ State complexity of combined operations ⋮ Random Deterministic Automata ⋮ State complexity of combined operations for suffix-free regular languages ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Average case analysis of Moore's state minimization algorithm ⋮ Usefulness of information and decomposability of unary regular languages ⋮ Average complexity of partial derivatives for synchronised shuffle expressions ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ Usefulness of information and unary languages ⋮ On the average state and transition complexity of finite languages ⋮ Random generation of DFAs ⋮ Complementing unary nondeterministic automata ⋮ Estimation of state complexity of combined operations ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ State complexity of basic operations on suffix-free regular languages ⋮ Average complexity of Moore's and Hopcroft's algorithms ⋮ Descriptional complexity of regular languages ⋮ Enumerating regular expressions and their languages ⋮ Prefix-Free Subsets of Regular Languages and Descriptional Complexity

This page was built for publication: