scientific article; zbMATH DE number 194974

zbMath0734.68001MaRDI QIDQ4692941

Derick Wood

Publication date: 5 June 1993

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

zbMATH Keywords

data compressionpattern matchingparsingtransducersNP- completenesstext editingsyntax diagramscomplexity propertiesclosure properties, decidability propertiesfinite automata, regular expressions, context- free grammars, pushdown automat, Turing machineslanguages and computation

Mathematics Subject Classification ID

Related Items (78)

Active symbols in grammars with valuations ⋮ Palindrome words and reverse closed languages ⋮ Deterministic soliton automata with at most one cycle ⋮ Greibach normal form transformation, revisited ⋮ INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES ⋮ One-unambiguity of regular expressions with numeric occurrence indicators ⋮ Generalizations of Code Languages with Marginal Errors ⋮ OVERLAP-FREE LANGUAGES AND SOLID CODES ⋮ On the decidability of infix inclusion problem ⋮ The validation of SGML content models ⋮ Obtaining shorter regular expressions from finite-state automata ⋮ On the definition of stochastic λ-transducers ⋮ Constructions for alternating finite automata^∗ ⋮ Pseudoknot-generating operation ⋮ On the existence of prime decompositions ⋮ Duplications and Pseudo-Duplications ⋮ Space filling curves and their use in the design of geometric data structures ⋮ State complexity of combined operations for suffix-free regular languages ⋮ Unnamed Item ⋮ Space-filling curves and their use in the design of geometric data structures ⋮ P systems with minimal insertion and deletion ⋮ A GRAMMAR-THEORETIC TREATMENT OF MULTIAGENT SYSTEMS ⋮ Decidability of involution hypercodes ⋮ Weak inverse neighborhoods of languages ⋮ Single semi-contextual insertion-deletion systems ⋮ Left is Better Than Right for Reducing Nondeterminism of NFAs ⋮ Edit-Distance Between Visibly Pushdown Languages ⋮ Efficient algorithms for computing the inner edit distance of a regular language via transducers ⋮ Provably Shorter Regular Expressions from Deterministic Finite Automata ⋮ Complexity of E0L structural equivalence ⋮ Pumping and pushdown machines ⋮ BOND-FREE LANGUAGES: FORMALIZATIONS, MAXIMALITY AND CONSTRUCTION METHODS ⋮ The inclusion problem for some subclasses of context-free languages ⋮ Structural equivalence and ET0L grammars ⋮ An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata ⋮ Synchronization ⋮ Generalizations of 1-deterministic regular languages ⋮ Local languages ⋮ Image Representation using Distributed Weighted Finite Automata ⋮ One-unambiguous regular languages ⋮ One-unambiguous regular languages ⋮ Equivalent language models that closely simulate one another and their illustration in terms ofLsystems ⋮ On Simon's congruence closure of a string ⋮ How expressions can code for automata ⋮ From regular expressions to finite automata^∗ ⋮ Enumerated BSP Automata ⋮ Subset construction complexity for homogeneous automata, position automata and ZPC-structures ⋮ Normal form algorithms for extended context-free grammars ⋮ State complexity of deletion and bipolar deletion ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ Reversible parallel communicating finite automata systems ⋮ On the number of active states in finite automata ⋮ UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES ⋮ THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA ⋮ Deterministic Lindenmayer Systems with Dynamic Control of Parallelism ⋮ Generalizations of Code Languages with Marginal Errors ⋮ Implementation of State Elimination Using Heuristics ⋮ State complexity of basic operations on suffix-free regular languages ⋮ Terminating left-hand sides of scattered context productions M. Nivat ⋮ The complete-tree-like matching mc-DFA and their implementation ⋮ A note on mc-DFA and its minimization ⋮ Context-freeness of the power of context-free languages is undecidable ⋮ An efficient null-free procedure for deciding regular language membership ⋮ Efficient implementation of regular languages using reversed alternating finite automata ⋮ Bound-decreasing duplication system ⋮ Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997 ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Regular Expressions and Transducers Over Alphabet-Invariant and User-Defined Labels ⋮ Greibach normal form transformation revisited. ⋮ SGML and XML document grammars and exceptions ⋮ DFA minimization: double reversal versus split minimization algorithms ⋮ Regular expressions into finite automata ⋮ Decidability of structural equivalence of E0L grammars ⋮ Decidability of EDT0L structural equivalence ⋮ On Simon's congruence closure of a string ⋮ Deterministic soliton automata with a single exterior node ⋮ Approximate matching between a context-free grammar and a finite-state automaton ⋮ Efficient enumeration of regular expressions for faster regular expression synthesis

This page was built for publication: