scientific article; zbMATH DE number 1517989
From MaRDI portal
zbMath0980.68066MaRDI QIDQ4506483
John E. Hopcrofts, Jeffrey D. Ullman, Rajeev Motwani
Publication date: 17 October 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45)
Related Items
Grammar-Based Integer Programming Models for Multi-Activity Shift Scheduling, \textit{The critic as artist}: Oscar Wilde's prolegomena to shape grammars, Combining Graph Transformation and Algebraic Specification into Model Transformation, Using finite state automata (FSA) for formal modelling of affordances in human-machine cooperative manufacturing systems, Active XML document rewriting based on tree automata theory, Generalized language measure families of probabilistic finite state systems, Equivalence in automata theory based on complete residuated lattice-valued logic, Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words, One-unambiguity of regular expressions with numeric occurrence indicators, The Generative Power of Probabilistic and Weighted Context-Free Grammars, Generalizations of Code Languages with Marginal Errors, Modeling for Verification, On the decidability of semigroup freeness, Universal Sleptsov net, Polymorphic P Systems with Non-cooperative Rules and No Ingredients, Unnamed Item, Efficient algorithms for regular expression constrained sequence alignment, Trace Semantics for IPDL, Metabolic isotopomer labeling systems. III: Path tracing, The \$-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems, Algorithmic complexity as a criterion of unsolvability, Deciding Regular Expressions (In-)Equivalence in Coq, Well-structured languages, Parameterized complexity classes beyond para-NP, Faster exact distributions of pattern statistics through sequential elimination of states, Time window temporal logic, Boolean language operations on nondeterministic automata with a pushdown of constant height, Model approach to grammatical evolution: theory and case study, Modeling Musical Structure with Parametric Grammars, Complexity of Promise Problems on Classical and Quantum Automata, Verification of finite-state machines: a distributed approach, The Word Problem for Finitely Presented Quandles is Undecidable, A new certificate for copositivity, String compression in FA-presentable structures, Distributional learning of conjunctive grammars and contextual binary feature grammars, Model checking of pushdown systems for projection temporal logic, On a class of irregular languages, Parametric Language Analysis of the Class of Stop-and-Wait Protocols, Formal languages for integer programming modeling of shift scheduling problems, The growth of iterates of multivariate generating functions, Ideal separation and general theorems for constrained synchronization and their application to small constraint automata, A pumping lemma for flip-pushdown languages, Secure communications with strange planet protocol, The Evolutionary Resilience of Distributed Cellular Computing, Learning Left-to-Right and Right-to-Left Iterative Languages, More Concise Representation of Regular Languages by Automata and Regular Expressions, Modeling time criticality of information, Dynamic Complexity of the Dyck Reachability, Natural Language Processing, Moving from Rules to Data, Incompleteness Theorems, Large Cardinals, and Automata over Finite Words, Characterization of Star-Connected Languages Using Finite Automata, Evaluation of language measure parameters for discrete event manufacturing systems with multiproduct machines, Hyper-minimizing minimized deterministic finite state automata, Translation from classical two-way automata to pebble two-way automata, The word problem for visibly pushdown languages described by grammars, Magic numbers in the state hierarchy of finite automata, A note on occurrence of gapped patterns in i.i.d. Sequences, Synchronous cooperation for explicit multi-threading, Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages, Simple permutations: Decidability and unavoidable substructures, Simulating Turing machines on Maurer machines, Regular splicing languages and subclasses, Parsing with a finite dictionary, On-line identification of language measure parameters for discrete-event supervisory control, Linear splicing and syntactic monoid, Weighted path queries on semistructured databases, Computational power of infinite quantum parallelism, Hopcroft’s Minimization Technique: Queues or Stacks?, Computation in Sofic Quantum Dynamical Systems, A Coinductive Animation of Turing Machines, BL-general fuzzy automata and accept behavior, On the Language of Primitive Partial Words, Composition of Use Cases Using Synchronization and Model Checking, Unnamed Item, Interactive proofs with quantum finite automata, A Kleene Theorem for Polynomial Coalgebras, Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata, Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata, Analysing Complexity in Classes of Unary Automatic Structures, Hairpin Structures in DNA Words, Incremental DFA Minimisation, Finite Automata for Generalized Approach to Backward Pattern Matching, Better Hyper-minimization, Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space, Two Results on Discontinuous Input Processing, Separating Codes and Traffic Monitoring, On the computation of entropy prior complexity and marginal prior distribution for the Bernoulli model, On the power of circular splicing, Some problems in automata theory which depend on the models of set theory, On decidability of list structures, A boundary result on enhanced time-varying distributed H systems with parallel computations, Inflations of geometric grid classes of permutations, Primitive Sets of Nonnegative Matrices and Synchronizing Automata, Coordination through de Bruijn sequences, Recursively Generated Evolutionary Turing Machines and Evolutionary Automata, The exact complexity of the infinite Post Correspondence Problem, An Extended Strange Planet Protocol, Existence of constants in regular splicing languages, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Undecidable Control Conditions in Graph Transformation Units, Fast learning of restricted regular expressions and dtds, Solving the parity problem in one-dimensional cellular automata, Reachability problems on reliable and lossy queue automata, Fuzzy languages with infinite range accepted by fuzzy automata: pumping lemma and determinization procedure, Matching regular expressions on uncertain data, Application of the trace assertion method to the specification, design, and verification of automaton programs, A power-set construction for reducing Büchi automata to non-determinism degree two, Computing equilibria: a computational complexity perspective, Linear algorithm for lexicographic enumeration of CFG parse trees, Objective computation versus subjective computation, Infinite games specified by 2-tape automata, An approximation algorithm for state minimization in 2-MDFAs, The state complexity of random DFAs, A geometric characterization of automatic semigroups, Modeling grammatical evolution by automaton, On dynamic topological and metric logics, Generating, sampling and counting subclasses of regular tree languages, Stability and robustness of planar switching linear systems, A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module, Frontiers of tractability for typechecking simple XML transformations, A characterization of (regular) circular languages generated by monotone complete splicing systems, Solutions of equations in languages, Preventing injection attacks with syntax embeddings, Processes with infinite liveness requirements, On the minimization of XML schemas and tree automata for unranked trees, Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source, Tree shuffle, State complexity of star of union and square of union on \textit{k} regular languages, A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem, Subsequential transducers: a coalgebraic perspective, Size lower bounds for quantum automata, Controlled finite automata, Testing DNA code words properties of regular languages, On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns, An inner product space on irreducible and synchronizable probabilistic finite state automata, Pseudorandom generators against advised context-free languages, State complexity of union and intersection of star on \(k\) regular languages, A graph theoretic approach to automata minimality, Automata theory based on lattice-ordered semirings, Doubly-constrained LCS and hybrid-constrained LCS problems revisited, \(E\)-unification with constants vs. general \(E\)-unification, Vector space formulation of probabilistic finite state automata, State complexity of combined operations with two basic operations, The size-cost of Boolean operations on constant height deterministic pushdown automata, Immunity and pseudorandomness of context-free languages, Scheme inclusion verification algorithm in algebraic model of programs with constants, Exact synchronization for finite-state sources, The automata that define representations of monomial algebras., Three research directions in non-uniform cellular automata, Program verification using symbolic game semantics, Learning register automata: from languages to program structures, Computation in finitary stochastic and quantum processes, On length-separating test tube systems, A Gel'fand-type spectral radius formula and stability of linear constrained switching systems, On the equivalence of stationary and finite-nonstationary nondeterministic automata, On translating Lambek grammars with one division into context-free grammars, Alternating space is closed under complement and other simulations for sublogarithmic space, Automata for unordered trees, Two double-exponential gaps for automata with a limited pushdown, Quantum finite automata: advances on Bertoni's ideas, The domino problem of the hyperbolic plane is undecidable, Z3str2: an efficient solver for strings, regular expressions, and length constraints, Constrained sequence analysis algorithms in computational biology, Approximate XML structure validation based on document-grammar tree similarity, Automata theory based on complete residuated lattice-valued logic: Turing machines, Strong emergence of wave patterns on Kadanoff sandpiles, Juxtaposing Catalan permutation classes with monotone ones, More concise representation of regular languages by automata and regular expressions, Second-level algorithms, superrecursivity, and recovery problem in distributed systems, Collaborative planning with confidentiality, Hoare logic-based genetic programming, An improved algorithm for determinization of weighted and fuzzy automata, Some results on the structure of unary unambiguous automata, A large neighbourhood search approach to the multi-activity shift scheduling problem, Acyclic networks maximizing the printing complexity, Turing machines, transition systems, and interaction, Intrinsic quantum computation, On regular temporal logics with past, Incremental learning with temporary memory, Automata theory based on complete residuated lattice-valued logic: Reduction and minimization, State complexity of union and intersection of square and reversal on \(k\) regular languages, Analysis and control of fuzzy discrete event systems using bisimulation equivalence, An elementary proof of a generalization of double Greibach normal form, The enumeration of permutations sortable by pop stacks in parallel, Solving path problems on the GPU, Maximal bifix codes of degree 3, A theory of ultimately periodic languages and automata with an application to time granularity, Powers of rationals modulo 1 and rational base number systems, Blocking of group automata. II: Mutual interlocking., A Rice-style theorem for parallel automata, Abstract models for dialogue protocols, Processes with local and global liveness requirements, On \(\tau\)-adic representations of integers, Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition, On the closure of pattern expressions languages under intersection with regular languages, An application of quantum finite automata to interactive proof systems, Statistical mechanics of complex systems for pattern identification, Regularity of a dynamic neighborhood of a regular language, Agent-based modeling of the context dependency in T cell recognition, Algorithmic aspects of decomposition and equivalence of finite-valued transducers, Lossiness of communication channels modeled by transducers1, The State Complexity of Lexicographically Smallest Words and Computing Successors, A Study of a Simple Class of Modifiers: Product Modifiers, Computational Hardness of Multidimensional Subtraction Games, Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, Counting clusters in a coloring grid, If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser, Circular splicing and regularity, LIPSCHITZ EQUIVALENCE OF SELF-SIMILAR SETS AND FINITE-STATE AUTOMATON, Minimal auxiliary Markov chains through sequential elimination of states, A decidable timeout-based extension of linear temporal logic, Sequential Relational Decomposition, Characterizing regular languages with polynomial densities, Unnamed Item, Unnamed Item, Random graph languages, Interleaving vs True Concurrency: Some Instructive Security Examples, Never-stop context-free learning, Prefix monoids of groups and right units of special inverse monoids, A survey on compositional algorithms for verification and synthesis in supervisory control, On closure properties of \(\mathcal{L}\)-valued linear languages, Approximate NFA universality and related problems motivated by information theory, Pumping lemmas for classes of languages generated by folding systems, Finite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and Permutations, Compositional Specification in Rewriting Logic, The genus of regular languages, The Computing Power of Determinism and Reversibility in Chemical Reaction Automata, Bisimulations of Boolean Control Networks, Unnamed Item, General Framework, Unnamed Item, Unnamed Item, Unnamed Item, Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words, Context-Freeness of Parsing Expression Languages is Undecidable, Boundedness problems for Minsky counter machines, Unnamed Item, Unnamed Item, A hierarchy of tree-automatic structures, Long-Run Average Behavior of Vector Addition Systems with States, Agent-Based Modeling, Mathematical Formalism for, Calculational design of a regular model checker by abstract interpretation, MINIMIZATION OF CONTEXT-FREE GRAMMARS, A Locally Optimal Algorithm for Estimating a Generating Partition from an Observed Time Series and Its Application to Anomaly Detection, Minimal Size of Counters for (Real-Time) Multicounter Automata, Products of ‘transitive” modal logics, Complexity of qualitative timeline-based planning, Boundedness problems for Minsky counter machines, Tree Process Calculus, Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs, Context-Bounded Analysis of TSO Systems, Linear Parsing Expression Grammars, Over Which Monoids is the Transducer Determinization Procedure Applicable?, Language-measure-theoretic optimal control of probabilistic finite-state systems, Unnamed Item, Unnamed Item, Perfect Discrimination Graphs: Indexing Terms with Integer Exponents, The computational power of parsing expression grammars, Infinitude of Primes Using Formal Languages, Complement for two-way alternating automata, Learners based on transducers, Weak Inclusion for XML Types, Bouma2 – A High-Performance Input-Aware Multiple String-Match Algorithm, The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata, State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal, Watson-Crick palindromes in DNA computing, On the regularity of circular splicing languages: a survey and new developments, A general architecture of oritatami systems for simulating arbitrary finite automata, Regular expression length via arithmetic formula complexity, On-line path computation and function placement in SDNs, Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata, A DRIVEN IFS REPRESENTATION OF TURING MACHINES, Input-driven pushdown automata for edit distance neighborhood, Unnamed Item, Equations, Contractions, and Unique Solutions, Enumerating permutations sortable by \(k\) passes through a pop-stack, Highly Undecidable Problems For Infinite Computations, Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS, Fuzzy pushdown automata, Tracing compressed curves in triangulated surfaces, Regular and linear permutation languages, Simulations by Time-Bounded Counter Machines, Foundations of RDF Databases, Semicomputable points in Euclidean spaces, A congruence-based perspective on automata minimization algorithms, Unnamed Item, Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference, The halting problem and security’s language-theoretic approach: Praise and criticism from a technical historian, Unnamed Item, Unnamed Item, Palindromic Characteristic of Committed Graphs and Some Model Theoretic Properties, Membership Problem for Two-Dimensional General Row Jumping Finite Automata, Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata, A Proof of Parikh’s Theorem via Dickson’s Lemma, Progressive events in supervisory control and compositional verification, p-values for the Discrete Scan Statistic through Slack Variables, A Decision Procedure for Guarded Separation Logic Complete Entailment Checking for Separation Logic with Inductive Definitions, The net automaton of a rational expression, On the impact of player capability on congestion games, Parameter synthesis in Markov models: a gentle survey, Descriptional Complexity of Non-Unary Self-Verifying Symmetric Difference Automata, On the computational power of swarm automata using agents with position information, Symbolic encoding of LL(1) parsing and its applications, An interval temporal logic characterization of extended \(\omega\)-regular languages, On Usefulness of Information: Framework and NFA Case, Better automata through process algebra, A Myhill-Nerode theorem for finite state matrix automata and finite matrix languages, Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages, On the hierarchy of swarm-automaton for the number of agents, Spiking neural P systems with weights and delays on synapses, A provably stable neural network Turing machine with finite precision and time, Binary coded unary regular languages, Recognizability in residuated lattices, Mixed Integer Linear Programming Approach for Control Synthesis with Weighted Signal Temporal Logic, Unnamed Item, Unnamed Item, Unnamed Item, State complexity of binary coded regular languages, Generalizations of Code Languages with Marginal Errors, Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds., Error tolerance for the recognition of faulty strings in a regulated grammar using fuzzy sets, Interval type-2 fuzzy automata and interval type-2 fuzzy grammar, Spiking neural P systems with a flat maximally parallel use of rules, On typical hesitant fuzzy automata, Combining Benders decomposition and column generation for multi-activity tour scheduling, Second-order finite automata, Passive testing with asynchronous communications and timestamps, Regular language representations in the constructive type theory of Coq, Growth in higher Baumslag-Solitar groups, Operational complexity and pumping lemmas, Stochastic analysis of minimal automata growth for generalized strings, Regular patterns, regular languages and context-free languages, A closeness- and priority-based logical study of social network creation, Path resolution for nested recursive modules, Isomorphism between two BL-general fuzzy automata, Weak call-by-value lambda calculus as a model of computation in Coq, Implementation relations and test generation for systems with distributed interfaces, Inductive synthesis of cover-grammars with the help of ant colony optimization, Semiautomatic structures, On the computation of counterexamples in compositional nonblocking verification, Disturbance decoupling in nonlinear hybrid systems, On the gap between separating words and separating their reversals, Coding tree languages based on lattice-valued logic, Model approach to grammatical evolution: deep-structured analyzing of model and representation, Separating codes and traffic monitoring, Deriving generic bounds for time-series constraints based on regular expressions characteristics, Partition refinement of component interaction automata, A note on automatic semigroups., On the adoption of abductive reasoning for time series interpretation, Finite transducers and nondeterministic state complexity of regular languages, Zombie number of the Cartesian product of graphs, Equidecomposable magmas, Closure and decidability properties of some language classes with respect to ciliate bio-operations., Introducing synchrony in fuzzy automata, Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank, Multi-matching nested relations, A language measure for supervisory control, Algorithmic complexity of recursive and inductive algorithms, Experience, generations, and limits in machine learning, Negotiation as concurrency primitive, Team bisimilarity, and its associated modal logic, for BPP nets, An adaptive subdivision method for root finding of univariate polynomials, Constrained synchronization and commutativity, Some studies in hemirings by the falling fuzzy \(k\)-ideals, Theory of reaction automata: a survey, ptype: probabilistic type inference, Quantifying matrix product state, Efficient determinization of visibly and height-deterministic pushdown automata, Multiple context-free tree grammars: lexicalization and characterization, A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem, Spiking neural P systems with target indications, Removing nondeterminism in constant height pushdown automata, On the decidability of subtyping with bounded existential types and implementation constraints, Concrete digital computation: what does it take for a physical system to compute?, Complementing unary nondeterministic automata, Patterns in words and languages, On expressive power of regular realizability problems, Design and implementation of bounded-length sequence variables, Semigroups arising from asynchronous automata., Finite automata and pattern avoidance in words, Computational complexity of synchronization under regular commutative constraints, A language measure for performance evaluation of discrete-event supervisory control systems, The structure of reflexive regular splicing languages via Schützenberger constants, On membrane hierarchy in P systems, On properties of bond-free DNA languages, Visibly linear dynamic logic, Unique decipherability in formal languages, Moments of the count of a regular expression in a heterogeneous random sequence, Dynamic preference logic meets iterated belief change: representation results and postulates characterization, Subroutines in P systems and closure properties of their complexity classes, Limit cycle analysis in a class of hybrid systems, Extending greedy feature selection algorithms to multiple solutions, Online premeans and their computation complexity, The descriptional power of queue automata of constant length, On decidability of theories of regular languages, General decidability results for asynchronous shared-memory programs: higher-order and beyond, Communicating reaction systems with direct communication, On the Hopcroft's minimization technique for DFA and DFCA, Compositionally progressive solutions of synchronous FSM equations, Deciding equivalence of top-down XML transformations in polynomial time, The computational capability of chemical reaction automata, A class of restricted P colonies with string environment, Arithmetic and \(k\)-maximality of the cyclic free magma, Cell-like spiking neural P systems with evolution rules, A characterization of regular circular languages generated by marked splicing systems, A game-semantic model of computation, Call-by-value lambda calculus as a model of computation in Coq, Computational bounds on polynomial differential equations, On regular tree languages and deterministic pushdown automata, Extracting symbolic knowledge from recurrent neural networks -- a fuzzy logic approach, Automata theory based on complete residuated lattice-valued logic: Pushdown automata, Pumping Lemma in context-free grammar theory based on complete residuated lattice-valued logic, Comparison of path-complete Lyapunov functions via template-dependent lifts, Gardens of Eden in the game of life, Active matter as a path planning interpreter, Formalization of the computational theory of a Turing complete functional language model, A non-ambiguous decomposition of regular languages and factorizing codes, State complexity of binary coded regular languages, Approximate NFA universality motivated by information theory
