scientific article; zbMATH DE number 3311755
From MaRDI portal
Publication:5592246
zbMath0196.01701MaRDI QIDQ5592246
Jeffrey D. Ullman, John E. Hopcrofts
Publication date: 1969
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Finite automata-models for the investigation of dynamical systems, When is a pair of matrices mortal?, The grammar of mammalian brain capacity, The full quotient and its closure property for regular languages, Decision problems for word-hyperbolic semigroups, An application of Poénaru's ``zipping theory, Singular propositions, negation and the square of opposition, Decidable sentences of Church-Rosser congruences, On some decision questions concerning pushdown machines, A relationship between two-dimensional finite automata and three-way tape-bounded two-dimensional Turing machines, Deletion along trajectories, The language intersection problem for non-recursive context-free grammars, Automata theory based on quantum logic: Some characterizations, The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Algorithmic uses of the Feferman-Vaught theorem, Complexity of multi-head finite automata: origins and directions, Algebraic Myhill-Nerode theorems, Optimal grids for five-axis machining, Fixed points avoiding abelian \(k\)-powers, Block insertion and deletion on trajectories, Construction of minimal deterministic finite automata from biological motifs, Algebraic structures of automata, Finite automata theory with membership values in lattices, A theory of computation based on unsharp quantum logic: finite state automata and pushdown automata, The expressive power of analog recurrent neural networks on infinite input streams, Another approach to the equivalence of measure-many one-way quantum finite automata and its application, Descriptional complexity of two-way pushdown automata with restricted head reversals, Groups, graphs, languages, automata, games and second-order monadic logic, Binary bubble languages and cool-lex order, Expected distance between terminal nucleotides of RNA secondary structures, Quasi-rocking real-time pushdown automata, Hardness of preorder checking for basic formalisms, Immunity and pseudorandomness of context-free languages, Multipass automata and group word problems, Computing power of Turing machines in the framework of unsharp quantum logic, A shrinking lemma for indexed languages, A lower bound technique for the size of nondeterministic finite automata, The element distinctness problem on one-tape Turing machines, Partial derivatives of regular expressions and finite automaton constructions, Monotonic and dual monotonic language learning, Time lower bounds do not exist for CRCW PRAMs, Computing with infinitary logic, Extremal solutions of inequations over lattices with applications to supervisory control, Quasi-deterministic 0L systems and their representation, Complexity results for 1-safe nets, An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata, Effective category and measure in abstract complexity theory, Approximately matching context-free languages, A remark on a paper by A.B. Matos, Universal computation and other capabilities of hybrid and continuous dynamical systems, An algebraic approach to hybrid systems, Completeness results concerning systolic tree automata and E0L languages, Valuations of languages, with applications to fractal geometry, Tie-breaking semantics and structural totality, Results on the use of category theory for the study of lattice-valued finite state machines, Promise problems solved by quantum and classical finite automata, Nondeterministic fuzzy automata with membership values in complete residuated lattices, The virtues of idleness: a decidable fragment of resource agent logic, Further remarks on DNA overlap assembly, Two double-exponential gaps for automata with a limited pushdown, Interactive proof systems and alternating time-space complexity, Recognising \(k\)-connected hypergraphs in cubic time, Decision problems and regular chain code picture languages, Algebraic and calculus query languages for recursively typed complex objects, Parametric runtime verification is NP-complete and coNP-complete, On the complexity of queries in the logical data model, The operation \(\uparrow\) on formal power series, Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements, On the complexity of minimizing probabilistic and quantum automata, Disjunctivity and other properties of sets of pseudo-bordered words, Rewriting of regular expressions and regular path queries, Bideterministic automata and minimal representations of regular languages, A coalgebraic approach to Kleene algebra with tests, Minimizing finite automata is computationally hard, Decidability of operation problems for T0L languages and subclasses, Decision problems for convex languages, Descriptional and computational complexity of finite automata -- a survey, Computational complexity of the problem of tree generation under fine-grained access control policies, Program equilibrium, Polynomial time learning of simple deterministic languages via queries and a representative sample, Survey of polynomial transformations between NP-complete problems, Structural properties of XPath fragments, Decidable containment of recursive queries, On reasoning about structural equality in XML: a description logic approach, Functions with local state: regularity and undecidability, Adding symbolic information to picture models: definitions and properties, On state-alternating context-free grammars, Avoiding large squares in infinite binary words, Walks in the quarter plane: Kreweras' algebraic model, Composing model programs for analysis, Nondeterministic fuzzy automata, One-reversal counter machines and multihead automata: revisited, Accepting networks of genetic processors are computationally complete, On the complexity of some extended word problems defined by cancellation rules, A lower bound for probabilistic algorithms for finite state machines, Basic tree transducers, Look-ahead on pushdowns, Partition semantics for relations, Turing complexity of the ordinals, Presentations of inverse monoids, Data-movement-intensive problems: Two folk theorems in parallel computation revisited, Nonuniform complexity and the randomness of certain complete languages, Some properties of space-bounded synchronized alternating Turing machines with universal states only, On the expressive power of finitely typed and universally polymorphic recursive procedures, Inverse monoids and rational Schreier subsets of the free group, Logically defined subsets of \(\mathbb{N}{}^ k\), AUTOMATE, a computing package for automata and finite semigroups, On nonconflicting languages that arise in supervisory control of discrete event systems, On controllability and normality of discrete event dynamical systems, Dynamic programming with convexity, concavity and sparsity, Pattern spectra, substring enumeration, and automatic sequences, The complexity of circuit value and network stability, The invariant problem for binary string structures and the parallel complexity theory of queries, Polynomial-time Abelian groups, A survey of space complexity, Lyapunov exponent spectrum for a generalized coupled map lattice, Fairness, distances and degrees, Extended regular expressions of arbitrary star degrees, Upper bounds on recognition of a hierarchy of non-context-free languages, A characterization of exponential-time languages by alternating context- free grammars, Relating attribute grammars and lexical-functional grammars, Recursively presented games and strategies, A lower bound for the nondeterministic space complexity of context-free recognition, \(\infty\)-regular temporal logic and its model checking problem, Testing logic programs for local stratification, A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space, On reversal-bounded picture languages, Non-associative parallel prefix computation, The parallel complexity of single rule logic programs, Complexity of logical theories involving coprimality, Complexity in left-associative grammar, Communication for alternating machines, Extensions to Barrington's M-program model, The complexity of matrix transposition on one-tape off-line Turing machines with output tape, The computational complexity of satisfiability of temporal Horn formulas in propositional linear-time temporal logic, Group presentations, formal languages and characterizations of one- counter groups, On the limit set of some universal cellular automata, A syntax-specification system for patterns, Automatic correction of syntax-errors in programming languages, A geometric hierarchy of languages, An improved bound for detecting looping configurations in deterministic PDA's, On tape-bounded complexity classes and multihead finite automata, On procedures as open subroutines. II, L-fuzzy grammars, Development systems with locally catenative formulas, Are two context-free languages translatable in a syntax-directed translation scheme?, A note on the ambiguity of context-free grammars, An observation on time-storage trade off, 1-way stack automaton with jumps, Space bounds for processing contentless inputs, Hierarchies of Turing machines with restricted tape alphabet size, Deterministic one-counter automata, Attributed translations, LL(1) grammars supporting an efficient error handling, SEMANOL (73), a metalanguage for programming the semantics of programming languages, Nonterminals versus homomorphisms in defining languages for some classes of rewriting systems, The Turing degree of the inherent ambiguity problem for context-free languages, The tape-complexity of context-independent developmental languages, A mathematical theory of learning transformational grammar, Ambiguity in the developmental systems of Lindenmayer, Space-bounded reducibility among combinatorial problems, Abstract families of length-preserving processors, Some properties of the class of \(L\) languages with interactions, A syntactic approach to fingerprint pattern recognition, A comparison of polynomial time reducibilities, Dynamics of discrete systems and pattern reproduction, Interactive languages, The derivation language of a phrase structure grammar, Formal grammars and the regeneration capability of biological systems, Polynomial and abstract subrecursive classes, A note on multiple-entry finite automata, Complexity measures for regular expressions, Deterministic Lindenmayer languages, nonterminals and homomorphisms, On the equivalence, containment, and covering problems for the regular and context-free languages, On the density of honest subrecursive classes, A result on the equivalence problem for deterministic pushdown automata, n-reconstructability of context-free grammars, Resolution of ambiguity in parsing, A useful device for showing the solvability of some decision problems, Nonexistence of program optimizers in several abstract settings, A relationship between ETOL and EDTOL languages, On the pre-AFL of \([lg\;n\) space and related families of languages], The halting problem for linear Turing assemblers, Relative complexity of checking and evaluating, A characterization of the power of vector machines, Finite automata with multiplication, On tape bounds for single letter alphabet language processing, Techniques for separating space complexity classes, Relating refined space complexity classes, Complete problems for deterministic polynomial time, Bracket-languages are recognizable in logarithmic space, On the decidability of the sequence equivalence problem for DOL-systems, The polynomial-time hierarchy, Bounds on the index and period of a binary relation on a finite set, Effective proper procedures and universal classes of program schemata, Regularity-preserving relations, Degree-languages: A new concept of acceptance, Computation sequence sets, Complexity-class-encoding sets, A recursive and a grammatical characterization of the exponential-time languages, Three-way automata on rectangular types over a one-letter alphabet, Three-way two-dimensional finite automata with rotated inputs, Random generation of combinatorial structures from a uniform distribution, Recurrent words and simultaneous growth in T0L systems, A pumping lemma for real-time deterministic context-free languages, Pattern selector grammars and several parsing algorithms in the context- free style, On the structure of one-tape nondeterministic Turing machine time hierarchy, Alternating on-line Turing machines with only universal states and small space bounds, The theory of ends, pushdown automata, and second-order logic, Finite automata play the repeated prisoner's dilemma, On solving star equations, On the regular equivalence problem for regular Thue systems, On \(\Delta ^ P_ 2\)-immunity, The space complexity of the unique decipherability problem, On pebble automata, On the complexity of theories of permutations, Approximation to measurable functions and its relation to probabilistic computation, Microeconomic foundations of cyclical irregularities or chaos, The problems of cyclic equality and conjugacy for finite complete rewriting systems, Pushdown machines for the macro tree transducer, A hierarchy of random-context grammars and automata, Infinite streams and finite observations in the semantics of uniform concurrency, The parallel complexity of deadlock detection, The undecidability of self-embedding for finite semi-Thue and Thue systems, Boolean delay equations. II: Periodic and aperiodic solutions, A Yacc extension for LRR grammar parsing, Concurrent program schemes and their logics, Parallel parsing of programming languages, Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery, High level tree transducers and iterated pushdown tree transducers, A note on complete problems for complexity classes, Several properties of array languages, The membership and equivalence problems for picture languages, On nondeterminism in parallel computation, A classification of complexity core lattices, The method of forced enumeration for nondeterministic automata, Language complexity on the synchronous anonymous ring, Two-dimensional iterative arrays: Characterizations and applications, Automata accepting primitive words, The interchange or pump (di)lemmas for context-free languages, Some relationships between logics of programs and complexity theory, Theory of traces, Isomorphisms and 1-L reductions, There are no fully space constructible functions between log log n and log n, Remarks on string-matching and one-way multihead automata, \(\Sigma_ 2SPACE(n)\) is closed under complement, Tape versus queue and stacks: The lower bounds, k\(+1\) heads are better than k for PDAs, Parallel algorithms for solvable permutation groups, Relativized alternation and space-bounded computation, On sparse oracles separating feasible complexity classes, Grammatical inference for even linear languages based on control sets, On the relative complexity of hard problems for complexity classes without complete problems, Pushdown automata with reversal-bounded counters, A note on three-way two dimensional alternating Turing machines, An incompleteness result in process algebra, Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time, Some considerations about NPRIORITY(1) without ROM, A generalization of automatic sequences, A pumping result for 2-context-free languages, Regular production systems and triangle tilings, Deterministic finite automata with recursive calls and DPDAs, Decimations of languages and state complexity, Small overlap monoids. I: The word problem., Small overlap monoids. II: Automatic structures and normal forms., Space-filling curves in adaptive curvilinear coordinates for computer numerically controlled five-axis machining, A formal approach to subgrammar extraction for NLP, On NFAs where all states are final, initial, or both, Detecting palindromes, patterns and borders in regular languages, Theory of one-tape linear-time Turing machines, Lattice-valued fuzzy Turing machines: computing power, universality and efficiency, An axiom system for sequence-based specification, Limitations of learning in automata-based systems, Real functions and numbers defined by Turing machines, A low and a high hierarchy within NP, Analyse numérique du problème des ondes longues en eau peu profonde, Init and Anf operating on \(\omega\)-languages, A note on the parallel computation thesis, Some undecidability results for non-monadic Church-Rosser Thue systems, A space-hierarchy result on two-dimensional alternating Turing machines with only universal states, An application of the matrix representation of transductions, The complexity of finding minimum-length generator sequences, Alternating simple multihead finite automata, Complexity and decidability for chain code picture languages, Hierarchies of hyper-AFLs, On proving time constructibility of functions, Restrictions on NLC graph grammars, Some results on subclass containment problems for special classes of dpda's related to nonsingular machines, Depth-first search is inherently sequential, The complexity of some decision problems about two-dimensional array grammars, Robust algorithms: a different approach to oracles, A linear time solution to the single function coarsest partition problem, The smallest automaton recognizing the subwords of a text, Exposure to deadlock for communicating processes is hard to detect, Parallel and sequential transformations on digital images, Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit, Variations on the technique of Ďuriš and Galil, An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape, Classes of regular and context-free languages over countably infinite alphabets, Complexity results on the conjugacy problem for monoids, A representation of recursively enumerable languages by two homomorphisms and a quotient, A unified framework for disambiguating finite transductions, Concatenation of inputs in a two-way automaton, A note on the reduction of two-way automata to one-way automata, Finite generation of ambiguity in context-free languages, Tradeoffs for language recognition on alternating machines, Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques, A pumping lemma for deterministic context-free languages, Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems, A grammatical characterization of alternating pushdown automata, A refined architecture for terminological systems: Terminology = Schema + Views, Comparisons of Parikh's condition to other conditions for context-free languages, Dynamical recognizers: real-time language recognition by analog computers, Algebraic processing of programming languages, PHRASE parsers from multi-axiom grammars, A communication hierarchy of parallel computations, Three-dimensional alternating Turing machines with only universal states, On a generalization of the Dyck-language over a two letter alphabet, Data representation and computational complexity, Halting space-bounded computations, A theorem on binary relations and infinite regular languages, Tree transducers, L systems, and two-way machines, One-way weak-stack-counter automata, On the complexity of \(\omega\)-type Turing acceptors, Codeterministic Lindenmayer schemes and systems, Indexings of subrecursive classes, Indirect addressing and the time relationships of some models of sequential computation, The node-deletion problem for hereditary properties is NP-complete, A note on closure properties of the classes of sets accepted by tape- bounded two-dimensional Turing machines, Cyclic closure properties of automata on a two-dimensional tape, Logical inference in English: A preliminary analysis, Deterministic simulation of tape-bounded probabilistic Turing machine transducers, Three-way tape-bounded two-dimensional Turing machines, Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines, On-line n-bounded multicounter automata, Three-way two-dimensional multicounter automata, Real-time recognition of two-dimensional tapes by cellular automata, Achievable high scores of \(\varepsilon\)-moves and running times in DPDA computations, The equivalence of r.e. program schemes and data flow schemes, Some new results on isotonic array grammars, A note on deterministic three-way tape-bounded two-dimensional Turing machines, \(\varepsilon\)-productions in context-free grammars, Multiple equality sets and Post machines, Observations on the complexity of regular expression problems, A note on decision problems for three-way two-dimensional finite automata, A closure property of deterministic context-free languages, Finding patterns common to a set of strings, An improved simulation result for ink-bounded Turing machines, Sequential and cellular graph automata, Computable queries for relational data bases, A space bound for one-tape multidimensional Turing machines, The nature of Soviet mathematical psychology, On time versus space. II, On time-space classes and their relation to the theory of real addition, On the time and tape complexity of weak unification, A parsing automata approach to LR theory, The finite power property for context-free languages, Extending lookahead for LR parsers, On tape-bounded probabilistic Turing machine acceptors, On the decidability of equivalence for deterministic pushdown transducers, Deciding Hadamard equivalence of Hadamard matrices, Position-restricted grammar forms and grammars, Two notions of correctness and their relation to testing, On universality of concurrent expressions with synchronization primitives, Some results on relativized deterministic and nondeterministic time hierarchies, The equivalence problem for LL- and LR-regular grammars, A note on rebound automata, A note on three-dimensional finite automata, Grammars with valuations - a discrete model for self-organization of biopolymers, The maximum flow problem is log space complete for P, Permutations are not context-free: An application of the interchange lemma, A pushdown automaton or a context-free grammar - which is more economical?, Fooling a two way automaton or one pushdown store is better than one counter for two way machines, The complexity of social groups and social systems described by graph structures, Symmetric space-bounded computation, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, The (generalized) Post correspondence problem with lists consisting of two words is decidable, The copying power of one-state tree transducers, On the computational complexity of satisfiability in propositional logics of programs, Pebble machines and tree walking machines, The limited regular languages, A time-luck tradeoff in relativized cryptography, The metalogic of economic predictions, calculations and propositions, Splicing semigroups of dominoes and DNA, Time-space tradeoffs for algebraic problems on general sequential machines, The string generating power of context-free hypergraph grammars, Average case completeness, Space bounded computations: Review and new separation results, Abstract grammars based on transductions, On multiple context-free grammars, Conflict detection and resolution in a lexical analyzer generator, The complexity of computing the number of strings of given length in context-free languages, Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems, Periodic orbits as the skeleton of classical and quantum chaos, Symbolic dynamics and characterization of complexity, Polynomial-time versus recursive models, Automatic groups and amalgams, Modal functions for concise definition of state machines and products, An analysis of fixed-point queries on binary trees, QRT FIFO automata, breadth-first grammars and their relations, Pattern expressions and pattern automata, On the computing power of fuzzy Turing machines, Deciding determinism of caterpillar expressions, Regulated nondeterminism in pushdown automata, The state complexity of \(L^{2}\) and \(L^k\), Periodic and Sturmian languages, Approximation of fuzzy context-free grammars, Notions of hyperbolicity in monoids., Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note, A genetic system based on simulated crossover of sequences of two-bit genes, On size reduction techniques for multitape automata, Iterated sequential transducers as language generating devices, An automata-theoretic approach to the word problem for \(\omega\)-terms over R, View-based query processing: on the relationship between rewriting, answering and losslessness, The origins of combinatorics on words, On the rational subset problem for groups., On the existence of prime decompositions, Context-dependent nondeterminism for pushdown automata, An equational logic based approach to the security problem against inference attacks on object-oriented databases, P systems with minimal parallelism, Undecidability of the bandwidth problem on linear graph languages, Honest polynomial time reducibilities and the \(P=?NP\) problem, The complexity of regular DNLC graph languages, Complexity and decidability for restricted classes of picture languages, Picture iteration and picture ambiguity, A note on ambiguity in context-free grammars, On attribute grammars without attribute synthesis, A theory of compaction-based parallelization, Sur les codes zigzag et leur décidabilité. (Zigzag codes and their decidability), Hypothetical datalog: Complexity and expressibility, Complexity-theoretic algebra. II: Boolean algebras, Distribution and synchronized automata, Efficient expansion of factored expressions, Introduction to graph grammars with applications to semantic networks, Bi-immunity results for cheatable sets, Learning indexed families of recursive languages from positive data: A survey, An efficient automata approach to some problems on context-free grammars., Finite automata for testing composition-based reconstructibility of sequences, Topological complexity of locally finite \(\omega\)-languages, The submonoid and rational subset membership problems for graph groups., Decision problems in membrane systems with peripheral proteins, transport and evolution, (Mem)brane automata, Bounded sequence testing from deterministic finite state machines, Post correspondence problem for short words, On deciding stability of multiclass queueing networks under buffer priority scheduling policies, The set of realizations of a max-plus linear sequence is semi-polyhedral, Qualitative reachability in stochastic BPA games, On probabilistic pushdown automata, Bounded regular path queries in view-based data integration, Detecting patterns in finite regular and context-free languages, Topological and measure-theoretic properties of one-dimensional cellular automata, Quasilinear cellular automata, Computational mechanics of cellular automata: an example, Pushdown dimension, Inclusion dynamics hybrid automata, On the size of Boyer-Moore automata, Fault-tolerant computation of distributed regular path queries, On small, reduced, and fast universal accepting networks of splicing processors, LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata, Space complexity of abelian groups, Malcev presentations for subsemigroups of direct products of coherent groups., Algorithms for learning regular expressions from positive data, Primitivity of finitely presented monomial algebras., The 4-way deterministic tiling problem is undecidable, Introduction to design choices in the semantics of Statecharts, Small cancellation theory and automatic groups, An undecidable problem about rational sets and contour words of polyominoes, Procedural languages for database queries and updates, Formulas for calculating supremal controllable and normal sublanguages, The zig-zag power series: A two-way version of the \({}^*\) operator., On Horn spectra, Expressive power of typed and type-free programming languages, Characterizations of one-way general quantum finite automata, Fuzzy alternating automata over distributive lattices, A note on alternating on-line Turing machines, Bandwidth constraints on problems complete for polynomial time, Groups, the theory of ends, and context-free languages, An application of array grammars to clustering analysis for syntactic patterns, Two-dimensional alternative Turing machines, Data structures for distributed counting, Homomorphic images of sentential form languages defined by semi-Thue systems, Towards a programming language based on the notion of two-level grammar, The complexity of monadic recursion schemes: Exponential time bounds, A tradeoff theorem for space and reversal, Linear indexed languages, Semi-linearity, Parikh-boundedness and tree adjunct languages, Stability in L systems, Minimal strings in a regular language with respect to a partial order on the alphabet, Formal languages and global cellular automaton behavior, Wolfram's class IV automata and a good Life, The complexity of matrix transposition on one-tape off-line Turing machines, On the connectedness of pictures in chain code picture languages, Extended automata-like regular expressions of star degree at most (2,1), On bounded interpretations of grammar forms, Safety and liveness of \(\omega\)-context-free languages, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Building reduced Petri net models of discrete manufacturing systems, On the undecidability of probabilistic planning and related stochastic optimization problems, Decidability of SHIQ with complex role inclusion axioms, On the growth of linear languages, Synchronized tree automata, On 1-inkdot alternating Turing machines with small space, Turbulent pattern bases for cellular automata, A pumping lemma and the structure of derivations in the boundary NLC graph languages, The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm, Nonuniform learnability, Canonical positions for the factors in paperfolding sequences, Probabilistic models of computer deadlock, Normal forms of deterministic grammars, A direct algorithm for checking equivalence of LL(k) grammars, ``V-tape, a virtual memory oriented data type, and its resource requirements, Direct or cascade product of pushdown automata, Complexity of some problems in Petri nets, On some questions of rationality and decidability, On LR(k) grammars and languages, Economy of description by parsers, DPDA's, and PDA's, A generalized approach to formal languages, C-grammars and tree-codifications, TIL systems and languages, Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages, Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition, Iterating iterated substitution, A unified approach to the generation and the acception of formal languages, Conditional Grammars, On a relation between algebraic programs and Turing machines, \(\omega\)-computations on Turing machines, Inference for regular bilanguages, Finite procedures for sofic systems, The game of \(N\) questions of a tree, Die Zeitkomplexität des Normalisierungsproblems bei kontextsensitiven Grammatiken, Some properties of two-dimensional on-line tessellation acceptors, An efficient decision procedure for the theory of rational order, Some relations between Markov algorithms and formal languages, A note on two-dimensional finite automata, On inverse deterministic pushdown transductions, Nondeterminism and Boolean operations in pda's, Monotone data flow analysis frameworks, Complexity metatheorems for context-free grammar problems, Extended linear macro grammars, iteration grammars, and register programs, \(\omega\)-computations on deterministic pushdown machines, Effective constructions in well-partially-ordered free monoids, Interpolazione e smoothing mono e bidimensionali relativi ad operatori differenziali lineari, Palindrome recognition in real time by a multitape Turing machine, Counting productions in context-free derivations, Stack languages and log n space, Lower bounds on space complexity for contextfree recognition, A definition of measures over language space, The concept of a linguistic variable and its application to approximate reasoning. I, Language operators related to Init, Some decidability results about regular and pushdown translations, A note on cyclic closure operations, Some decision problems concerning sequential transducers and checking automata, The concept of a linguistic variable and its application to approximate reasoning. II, The concept of a linguistic variable and its application to approximate reasoning. III, A useful lemma for context-free programmed grammars, Fast recognition of context-sensitive structures, One-way simple multihead finite automata, On equivalence of grammars through transformation trees, Characterizing the regular prefix codes and right power-bounded languages, Computing with graph rewriting systems with priorities, On the inference of strategies, Regular sequence operations and their use in database queries, Verifying identical communicating processes is undecidable, The end of pumping, Decidability of the finiteness of ranges of tree transductions, 2-testability and relabelings produce everything, Bridging across the \(\log(n)\) space frontier, Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, Language complexity of rotations and Sturmian sequences, The ancestor width of grammars and languages, Some undecidability results concerning the property of preserving regularity, Synchronization expressions with extended join operation, On well quasi orders of free monoids, A construction on finite automata that has remained hidden, On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group, On quasi orders of words and the confluence property, Transcendence of binomial and Lucas' formal power series, \(d\)-minimal languages, On computation with pulses, Deterministic generalized automata, Exact performance equivalence: An equivalence relation for stochastic automata, On the computational completeness of context-free parallel communicating grammar systems, Feasible graphs with standard universe, An inequality for non-negative matrices, Temporal connectives versus explicit timestamps to query temporal databases, Regular path queries with constraints, Cut and paste, On deciding trace equivalences for processes, The utilization of fuzzy sets in the recognition of imperfect strings, A description of dynamic behavior for compilers based on object oriented modeling, Regular expressions into finite automata, Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\), The word problem of inverse monoids presented by one idempotent relator, Transformations of one-dimensional cellular automaton rules by translation-invariant local surjective mappings, Nondeterministics circuits, space complexity and quasigroups, The state complexities of some basic operations on regular languages, Fluctuation spectroscopy, A comparative classification of complexity measures, Synthesis of real time acceptors, Decentralized state feedback control of discrete event systems, On the effects of noise and speed on computations, The complexity of optimizing finite-state transducers, Complex systems, complexity measures, grammars and model-inferring, On sparse languages \(L\) such that \(LL= \Sigma^*\), Graph groups are biautomatic, A note on the complexity of deciding bisimilarity of normed unary processes, Language equations over a one-letter alphabet with union, concatenation and star: A complete solution, On the solvability of domino snake problems, The complexity of connectivity problems on context-free graph languages, A note on multi-inkdot nondeterministic Turing machines with small space, Computational depth and reducibility, Computability with low-dimensional dynamical systems, On recursive bounds for the exceptional values in speed-up, On termination of one rule rewrite systems, Regularity and locality in \(k\)-terminal graphs, Invariant sets for substitution, Computing over the reals with addition and order, The generating power of boundary NLC graph grammars and cycle graphs, Periodic sets of integers, On the simulation of many storage heads by one, Universality of a reversible two-counter machine, On the computational power of dynamical systems and hybrid systems, The simple dynamics of super Turing theories, A family of universal recurrent networks, Complexity results for two-way and multi-pebble automata and their logics, On path equivalence of nondeterministic finite automata, About the \(p\)-paperfolding words, A polynomial algorithm for deciding bisimilarity of normed context-free processes, Lower bounds for one-way probabilistic communication complexity and their application to space complexity, Finite automata and ordinals, The complexity of PDL with interleaving, On the language of primitive words, Efficient simulations by a biased coin, VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states, Fuzzy semantic analysis and formal specification of conceptual knowledge, The isomorphism conjecture holds and one-way functions exist relative to an oracle, The bounded degree problem for eNCE graph grammars, Deciding true concurrency equivalences on safe, finite nets, Recursion theoretic characterizations of complexity classes of counting functions, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate, Reachability analysis of dynamical systems having piecewise-constant derivatives, The validation of SGML content models, Deterministic automata. Simulation, universality and minimality, Generating grammars for SGML tagged texts lacking DTD, Language-theoretic complexity of disjunctive sequences, On the sequentiality of the successor function, Complexity and categoricity, The single loop representations of regular languages, Growing context-sensitive languages and Church-Rosser languages, Logical description of context-free graph languages, On projective and separable properties, A hierarchy of eNCE families of graph languages, On the power of alternation on reversal-bounded alternating Turing machines with a restriction, Automaticity. II: Descriptional complexity in the unary case, Alternation on cellular automata, Dynamic constraints and object migration, On the computational power of self-stabilizing systems, On computational complexity of contextual languages, Pushdown automata with bounded nondeterminism and bounded ambiguity, A temporal logic for real-time partial ordering with named transactions, From regular expressions to DFA's using compressed NFA's, Permutations generated by token passing in graphs, Restrictions and representations of vector controlled concurrent system behaviours, Monadic logic programs and functional complexity, The set of reversible \(90/150\) cellular automata is regular, Program schemes, recursion schemes, and formal languages, Deterministic multitape automata computations, Generalized overlap resolvable grammars and their parsers, Controlled pushdown automata, Note on analogue memory automata, Finite automata on timed \(\omega\)-trees, Optimal insertion in deterministic DAWGs, Ambiguity in omega context free languages, Efficient minus and signed domination in graphs, A family of NFAs which need 2\(^{n}-\alpha\) deterministic states, Borel hierarchy and omega context free languages., McNaughton families of languages., On viewing block codes as finite automata., Nonterminal complexity of programmed grammars., Algebraic rewritings for optimizing regular path queries., Unambiguous Büchi automata., On the simulation of quantum Turing machines., The complexity of bisimilarity-checking for one-counter processes., Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars., Regular binoid expressions and regular binoid languages., Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions, The commutative closure of a binary slip-language is context-free: A new proof., System theory for system identification., A characterization of Thompson digraphs., Follow automata., On the entropy of regular languages., The homomorphism problem for trace monoids., Learning regular languages using RFSAs., Generalized acceptance, succinctness and supernondeterministic finite automata., Regular closed sets of permutations., An algebraic characterization of deterministic regular languages over infinite alphabets., Reducing NFAs by invariant equivalences., Continuous-time computation with restricted integration capabilities, Quantum automata and quantum grammars, Realtime subshifts, Some analytic features of algebraic data, Advanced elementary formal systems., Decision lists over regular patterns., Polynomial-time identification of very simple grammars from positive data., On algebraic and logical specifications of classes of regular languages., Alternating and empty alternating auxiliary stack automata., On omega context free languages which are Borel sets of infinite rank., On regular drawn symbolic picture languages, Automatic graphs and D0L-sequences of finite graphs, Many aspects of defect theorems, Taming the complexity of biochemical models through bisimulation and collapsing: theory and practice, On the decidability of the termination problem of active database systems, Characterizations of quantum automata, Closure properties of locally finite \(\omega\)-languages, Belief-based equilibrium, Updatable timed automata, Word-paired catenations of regular languages, Fuzzy alternating Büchi automata over distributive lattices, Verification complexity of a class of observational properties for modular discrete events systems, The lattice-valued Turing machines and the lattice-valued type 0 grammars, The inclusion problem for regular expressions, Reversible pushdown automata, Pregroup grammars with letter promotions: complexity and context-freeness, Mergible states in large NFA, Succinct representations of languages by DFA with different levels of reliability, On the descriptional power of heads, counters, and pebbles, On two-way communication in cellular automata with a fixed number of cells, Finite graph automata for linear and boundary graph languages, Algebraically complete semirings and Greibach normal form, A probabilistic model of computing with words, Attribute grammars for unranked trees as a query language for structured documents, The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages, Dynamically controlled cooperating/distributed grammar systems, Reasoning about strings in databases, In defense of the maximum entropy inference process, Cut, paste and filter., Bounds in the propagation of selection into logic programs, The infimal prefix-closed and observable superlanguage of a given language, The calculi of emergence: Computation, dynamics and induction, Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines, A note on two-dimensional probabilistic Turing machines, A probabilistic approach to navigation in Hypertext, Manipulating derivation forests by scheduling techniques, Bandwidth contrained NP-complete problems, Domino-tiling games, Some consequences of the existnce of pseudorandom generators, Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs, Membership problems for regular and context-free trace languages, The speed of copying on one-tape off-line turing machines, Reversible space equals deterministic space, Annotated fuzzy logic programs, Repetitiveness of languages generated by morphisms, Finite nondeterministic automata: simulation and minimality, On lengths of words in context-free languages, Shuffle and scattered deletion closure of languages, An efficient null-free procedure for deciding regular language membership, Using DNA to solve the bounded Post correspondence problem, The complexity of the word problems for commutative semigroups and polynomial ideals, Randomised algorithms, Enumeration of double cosets, A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages, Checking sets, test sets, rich languages and commutatively closed languages, Approximate string matching using factor automata, A characterization of local regular languages, Characterization of unary developmental languages, The length sets of D0L languages are uniformly bounded, Equivalenza tra grammatiche, sistemi di equazioni in variabili di linguaggio e serie formali, Time bounded random access machines, Normal forms for context-sensitive grammars, Theory of formal grammars, DOL sequences, Shuffle languages are in P, Double Greibach operator grammars, Automatic semigroups, A framework to visualize equivalences between computational models of regular languages., Simulating finite automata with context-free grammars., On the power of incremental learning., Canonical derivatives, partial derivatives and finite automaton constructions., Public data structures: counters as a special case., On the presence of periodic configurations in Turing machines and in counter machines., Extensions and submonoids of automatic monoids., Greibach normal form transformation revisited., Incremental concept learning for bounded data mining., Automata, Boolean matrices, and ultimate periodicity., Logic with equality: Partisan corroboration and shifted pairing, Recursive computational depth., Process rewrite systems., On the undecidability of second-order unification, Regular languages accepted by quantum automata, Non-closure property of space-bounded two-dimensional alternating Turing machines, Symbolic model checking of timed guarded commands using difference decision diagrams, On optimal control of a class of partially observed discrete event systems, Decidability of the consistency problem for regular symbolic picture description languages, Algorithms, nymphs, and shepherds, Sequential grammars and automata with valences, Counter machines, Query automata over finite trees, Decision algorithms for multiplayer noncooperative games of incomplete information, Variants of iterative learning, Algebraic aspects of families of fuzzy languages, The chop of languages, One-way reversible multi-head finite automata, A model for deadlock detection based on automata and languages theory, A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly, Scaling properties of generalized Carlitz sequences of polynomials, Minimization of lattice finite automata and its application to the decomposition of lattice languages, Comparing the size of NFAs with and without \(\epsilon\)-transitions, Characterization of realizable space complexities, Minimum-cost delegation in service composition, Rational subsets of partially reversible monoids, State complexity of combined operations, Finite turns and the regular closure of linear context-free languages, The word problem for nilpotent inverse monoids, Bayesian estimation and the Kalman filter, A brief account of runtime verification, Formal language identification: query learning vs. gold-style learning, Stability of discrete linear inclusion, Combinatorial representation of invariants of a soliton cellular automaton, A note on measures of fuzziness applied to nonmonotonic fuzzy propositional logic, Efficient testing and matching of deterministic regular expressions, Artin groups of extra-large type are biautomatic, Arity and alternation in second-order logic, Deletion operations on deterministic families of automata, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, On the splicing operation, Regularity of splicing languages, A generic framework for checking semantic equivalences between pushdown automata and finite-state automata, Finding the probability of infection in an SIR network is NP-hard, Question answering by humans and machines: a complexity-theoretic view, Playing the wrong game: an experimental analysis of relational complexity and strategic misrepresentation, The role of information processing cost as the foundation of bounded rationality in game theory, Computational power of two stacks with restricted communication, An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton, Acyclic automata and small expressions using multi-tilde-bar operators, Independent parallelism in finite copying parallel rewriting systems, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, Synchronization paradigm for protocol testing under multiparty configuration, Problem solving during artificial selection of self-replicating loops, Automata theory based on quantum logic: reversibilities and pushdown automata, Complexity theory for splicing systems, Deciding non-emptiness of hypergraph languages generated by connection-preserving fusion grammars is NP-complete, The inclusion problem for some subclasses of context-free languages, Magic numbers in the state hierarchy of finite automata, A general comparison of language learning from examples and from queries, On the existence of regular approximations, Transition complexity of language operations, A complete characterization of deterministic regular liveness properties, Prefix-free regular languages and pattern matching, A multiset-based model of synchronizing agents: Computability and robustness, The loop problem for Rees matrix semigroups., New operations and regular expressions for two-dimensional languages over one-letter alphabet, Incremental learning of context free grammars based on bottom-up parsing and search, Exact enumeration of acyclic deterministic automata, Maze recognizing automata and nondeterministic tape complexity, Classes of discrete optimization problems and their decision problems, On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids, A categorical approach to lattice-valued fuzzy automata, Fuzzy automata with \(\varepsilon\)-moves compute fuzzy measures between strings, Approximation and robustness of fuzzy finite automata, Graph splicing systems, Hierarchy and equivalence of multi-letter quantum finite automata, On the descriptional complexity of Watson-Crick automata, Estimation of state complexity of combined operations, Language operations with regular expressions of polynomial size, Classical and effective descriptive complexities of \(\omega \)-powers, The relationships among several types of fuzzy automata, Two dynamic programming algorithms for which interpreted pebbling helps, Determination of equivalence between quantum sequential machines, An alternative definition of splicing, Automated pattern detection -- an algorithm for constructing optimally synchronizing multi-regular language filters, Boolean operations and inclusion test for attribute-element constraints, Progressive solutions to a parallel automata equation, Small fast universal Turing machines, Algebraic properties of \(LA\)-languages, On the least number of palindromes in two-dimensional words, Determining the equivalence for one-way quantum finite automata, Weighted parsing for grammar-based language models over multioperator monoids, Closure properties in the class of multiple context-free groups, Syntax directed translations and the pushdown assembler, Relationships between nondeterministic and deterministic tape complexities, What makes some language theory problems undecidable, From decidability to undecidability by considering regular sets of instances, On the existence of generators for certain AFL, Time- and tape-bounded Turing acceptors and AFLs, Complexity problems in real time languages, Time-bounded grammars and their languages, On stochastic context-free languages, Der programmierbare endliche Automat. (The programmable finite automaton), LR(k) grammars and deterministic languages, On non-determinacy in simple computing devices, The stability of the deterministic Skorokhod problem is undecidable, Node replacement graph grammars with dynamic node relabeling, Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata, Automatic semigroup acts., Trimming visibly pushdown automata, Deterministic input-driven queue automata: finite turns, decidability, and closure properties, Unwinding biological systems, A formalisation of the Myhill-Nerode theorem based on regular expressions, Synchronous context-free grammars and optimal linear parsing strategies, Undecidability of the emptiness problem for context-free picture languages, Some formal results about stratificational grammars and their relevance to linguistics, A Formalisation of Finite Automata Using Hereditarily Finite Sets, Random context structure grammars and automata - a formal approach, A survey of two-dimensional automata theory, A characterization of constant-time cellular automata computation, Normal forms for phrase-structure grammars, Inverse monoids: decidability and complexity of algebraic questions., On some constructions of grammars for linear languages, Unnamed Item, Unnamed Item, The topology of language, A context-free language for binary multinomial processing tree models, Two-way automaton computations, Unnamed Item, Counting (Watson-Crick) palindromes in Watson-Crick conjugates, (Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars, Enumeration of two dimensional palindromes, Unnamed Item, Continuous Petri Nets: Expressive Power and Decidability Issues, Moore machines duality, Stochastic grammars and languages, Extension of tabled 0L-systems and languages, Array automata and operations on array languages, The Genesis of Fuzzy Sets and Systems – Aspects in Science and Philosophy, Sequential classification of strings generated by SCFG's, Relevance of computer science to linguistics and vice versa, A REGULARITY CONDITION FOR CONTEXT-FREE GRAMMARS, The size of LALR (1) parsers, Context free languages in biological systems, Description of developmental languages using recurrence systems, Context-sensitive languages and G-automata, Iterative tree arrays with logarithmic depth†, Description of restricted automata by first-order formulae, Inductive inference of context-free languages based on context-free expressions, On a family of acceptors for some classes of developmental languages, An error-correcting syntactic decoder for computer networks, Recursive generation of local adjunct languages, CONTINUOUS PETRI NETS: EXPRESSIVE POWER AND DECIDABILITY ISSUES, Forward Bisimulations for Nondeterministic Symbolic Finite Automata, Multiple inheritance in the class automaton model, Unnamed Item, Unnamed Item, Data schemata based on directed graphs, The notion of a probabilistic cellular acceptor, The applicability of program schema results to programs, On a code problem concerning planar acyclic graphs, Restricted one-counter machines with undecidable universe problems, ON GROUPS AND COUNTER AUTOMATA, Hierarchies of recursive computations†, Formal Languages and Groups as Memory, A homomorphic characterization of time and space complexity classes of languages†, Complexity of some problems concerningL systems, REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM, A Formalisation of the Myhill-Nerode Theorem Based on Regular Expressions (Proof Pearl), On the Formalization of Some Results of Context-Free Language Theory, Pure grammars and pure languages†, A note on dpda transductions of {0,1}∗and inverse dpda transductions of the dyck set, Substitution expressions, Moments of string and derivation lengths of stochastic context-free grammars, Finite-turn checking automata, Pushdown automata with counters, Writing stack acceptors, Unnamed Item, A homomorphism theorem for weighted context-free grammars, Direction controlled programmed grammars, Absolutely parallel grammars and two-way finite-state transducers, Tesselations with local transformations, The Markov algorithm as a language parser-linear bounds, The relation between derivations and syntactical structures in phrase- structure grammars, Free and almost-free subsemigroups of a free semigroup, LR-regular grammars - an extension of LR(k) grammars, N-fold fuzzy grammars, Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata, A note on multihead automata and context-sensitive languages, Eine einfache universelle Turingmaschine in ALGOL 60 Simulation, Strict deterministic grammars, THE IDEMPOTENT PROBLEM FOR AN INVERSE MONOID, The equivalence problem for deterministic TOL-systems is undecidable, Examples of formal grammars with weights, Real-time language recognition by one-dimensional cellular automata, A class of universal linear bounded automata, A remark on regularity of parallel languages, Solvable classes of discrete dynamic programming, On the Gödel class with identity, Some properties of one-pebble Turing machines with sublogarithmic space, A note on context free languages, complexity classes, and diagonalization, Space-bounded simulation of multitape turing machines, On free inverse monoid languages, The existential theory of equations with rational constraints in free groups is PSPACE-complete, A theory of computation based on quantum logic. I, Sublogarithmic ambiguity, Measuring nondeterminism in pushdown automata, Maximally permissive mutually and globally nonblocking supervision with application to switching control, Fuzzy context-free languages. I: Generalized fuzzy context-free grammars, Fuzzy context-free languages. II: Recognition and parsing algorithms, Quantum finite automata with control language, Learning erasing pattern languages with queries, Relations between Gold-style learning and query learning, Unnamed Item, Specifications and an implementation of the type-ambiguity problem in pascal, On the undecidability and descriptional complexity of synchronized regular expressions, Recognizability in residuated lattices, Palindrome words and reverse closed languages, Strong types for coordinating active objects, INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES, Unnamed Item, Homomorphisms of algebras, A note on one-way and two-way automata, A note on left-recursive rules and the partitioning of a recognition matrix for syntax-directed translation, Unnamed Item, Unnamed Item, EXTENDED FINITE AUTOMATA AND WORD PROBLEMS, A note of ins-primitive words, Unnamed Item, Subrecursiveness: Machine-independent notions of computability in restricted time and storage, Weak parallel machines: A new class of physically feasible parallel machine models, Characterization of context-pree languages by erasing automata, Two lower bounds on distributive generation of languages, Data editing and imputation from a computational point of view, Feasibly categorical models, HV-Palindromes in Two-Dimensional Words, Formal grammars for turn-bounded deterministic context-free languages, Some results in tree automata, Languages and P0L schemes, On deciding some equivalences for concurrent processes, Development systems with finite axiom sets, Literal homomorphisms of ol-languagest, Literal homomorphisms of ol-languagest, Necessary and sufficient conditions for a power language to be deterministic, Context-free preserving functions, Bottom-up and top-down tree transformations— a comparison, Combinatorial systems defined over one- and two-letter alphabets, OBJECTS, Parallel OL-languages, B-fuzzy grammars, Relativization of questions about log space computability, Solving constrained Pell equations, An analysis of Lambek's production machines, A survey of computational complexity results in systems and control, LANGUAGE PROCESSING BY DYNAMICAL SYSTEMS, Relationships between pushdown automata with counters and complexity classes, On the complexity of finite, pushdown, and stack automata, A technology for reverse-engineering a combinatorial problem from a rational generating function, Two-Dimensional Palindromes and Their Properties, Recursive turing machines †, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, A note on weak operator precedence grammars, A note on weak operator precedence grammars, Amalgamated free products of inverse semigroups, The systematic design of file-processing programs, On coupled languages and translations, Total complexity and the inference of best programs, Upper bound on the products of particle interactions in cellular automata, Locally finite languages, Deciding stability and mortality of piecewise affine dynamical systems, Pushdown automata, multiset automata, and Petri nets, Alternation for sublogarithmic space-bounded alternating pushdown automata, Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries, A PROPOSED MULTI‐VALUED EXTENSION TO ALGOL 68, Size, index, and context-sensitivity of controlled partition grammars, The stability of saturated linear dynamical systems is undecidable, Fuzzy automaton induction using neural network, APPLICATION OF FUZZY LANGUAGES TO PATTERN RECOGNITION, Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata, Comparing language operations, Top-down tree transducers with regular look-ahead, Prefix Primitive Languages, Rudimentary relations and stack languages, Easiness assumptions and hardness tests: Trading time for zero error, Time-space tradeoffs for SAT on nonuniform machines, On Computable Numbers, Nonuniversality, and the Genuine Power of Parallelism, Database semantics for natural language, On the power of Las Vegas II: Two-way finite automata, Analogies and differences between quantum and stochastic automata, Topological properties of omega context-free languages, Computational complexity of some problems involving congruences on algebras, On two-sided infinite fixed points of morphisms, Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time, Probabilistic rebound Turing machines, Constructible functions in cellular automata and their applications to hierarchy results, Two undecidability results for chain code picture languages, Wadge hierarchy of omega context-free languages, Minimal cover-automata for finite languages, Subset construction complexity for homogeneous automata, position automata and ZPC-structures, Church’s Problem and a Tour through Automata Theory, The complexity of the membership problem for some extensions of context-free languagest†, On the proof of a theorem by chomsky—hopcroft—ullman, Parsers for indexed grammars, Set-driven and rearrangement-independent learning of recursive languages, Word-paired insertions of languages, VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states, The computational limits to the cognitive power of the neuroidal tabula rasa, The object-oriented paradigm and automata theory, Unnamed Item, Unnamed Item, Invito alla teoria dei linguaggi formali, ALGORITHMS FOR FINDING CHOMSKY AND GREIBACH NORMAL FORMS FOR A FUZZY CONTEXT‐FREE GRAMMAR USING AN ALGEBRAIC APPROACH, An efficient algorithm for finding kleene closure of regular expression matrices, Three hierarchies of transducers, Representations of the language recognition problem for a theorem prover, A syntax directed macro processor, Some restrictions onW-grammars
