Intersection and union of regular languages and state complexity
From MaRDI portal
Publication:1199879
DOI10.1016/0020-0190(92)90198-5zbMath0763.68048OpenAlexW2008342226MaRDI QIDQ1199879
Publication date: 17 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90198-5
Related Items
Two-way machines and de Bruijn words, Once-Marking and Always-Marking 1-Limited Automata, On Boolean combinations forming piecewise testable languages, Descriptional Complexity of Input-Driven Pushdown Automata, State-complexity of finite-state devices, state compressibility and incompressibility, The state complexity of \(L^{2}\) and \(L^k\), State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach, COMPLEXITY IN UNION-FREE REGULAR LANGUAGES, STATE COMPLEXITY OF CODE OPERATORS, THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES, Nondeterministic state complexity of site-directed deletion, On the number of active states in deterministic and nondeterministic finite automata, Nondeterministic complexity of operations on free and convex languages, More on Deterministic and Nondeterministic Finite Cover Automata, From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods, State Complexity of Prefix Distance, State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs, Nondeterministic operational complexity in subregular languages, Unnamed Item, State complexity of inversion operations, The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic, The size of power automata., A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity, The nondeterministic state complexity of the site-directed deletion language operation, Operational state complexity revisited: the contribution of monsters and modifiers, Complexity of exclusive nondeterministic finite automata, State complexity of cyclic shift, On a Conjecture by Christian Choffrut, State Complexity of Insertion, On the descriptional complexity of stateless deterministic ordered restarting automata, On CD-systems of stateless deterministic R-automata with window size one, Concatenation of regular languages and descriptional complexity, Nondeterministic state complexity of star-free languages, DESCRIPTIONAL COMPLEXITY OF SPLICING SYSTEMS, Finite transducers and nondeterministic state complexity of regular languages, On the State Complexity of Complements, Stars, and Reversals of Regular Languages, DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET, Descriptional Complexity of the Forever Operator, Finite Automata, Palindromes, Powers, and Patterns, Theory of átomata, Operations on Unambiguous Finite Automata, Descriptional complexity of unambiguous input-driven pushdown automata, Classes of two-dimensional languages and recognizability conditions, Rewriting extended regular expressions, Succinct description of regular languages by weak restarting automata, Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages, Oblivious two-way finite automata: decidability and complexity, THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES, Further closure properties of input-driven pushdown automata, Lower Bound Methods for the Size of Nondeterministic Finite Automata Revisited, NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS, NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY, LIMITED AUTOMATA AND REGULAR LANGUAGES, State complexity of some operations on binary regular languages, Descriptional and computational complexity of finite automata -- a survey, Limitations of lower bound methods for deterministic nested word automata, State complexity of finite partial languages, State complexity of binary coded regular languages, Nondeterministic state complexity of nested word automata, On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's, Language operations with regular expressions of polynomial size, Operational state complexity of nested word automata, Lower bounds for the size of deterministic unranked tree automata, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Power, positive closure, and quotients on convex languages, Assisted Problem Solving and Decompositions of Finite Automata, Nondeterministic State Complexity of Star-Free Languages, On Restarting Automata with Window Size One, State Complexity of the Quotient Operation on Input-Driven Pushdown Automata, State Complexity of Nested Word Automata, Hairpin Structures in DNA Words, On the number of active states in finite automata, Regular expression length via arithmetic formula complexity, Input-driven pushdown automata for edit distance neighborhood, STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION, Largest common prefix of a regular tree language, MAGIC NUMBERS AND TERNARY ALPHABET, State complexity of power, State complexity of unique rational operations, Magic Numbers and Ternary Alphabet, Concatenation of Regular Languages and Descriptional Complexity, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, Unnamed Item, Descriptional Complexity of Bounded Regular Languages, Nondeterministic complexity in subclasses of convex languages, Descriptional complexity of regular languages, A logic for document spanners, Detecting palindromes, patterns and borders in regular languages, Nondeterministic Tree Width of Regular Languages, Universal Disjunctive Concatenation and Star, Deterministic blow-ups of minimal NFA's, Site-directed insertion: language equations and decision problems, State complexity of partial word finite automata, Simulating finite automata with context-free grammars., More on Minimizing Finite Automata with Errors — Nondeterministic Machines, State complexity of binary coded regular languages, Operations on subregular languages and nondeterministic state complexity, State complexity of finite partial languages, Yet another canonical nondeterministic automaton, More on deterministic and nondeterministic finite cover automata, State complexity of prefix distance
Cites Work
