scientific article; zbMATH DE number 3368555

zbMath0232.94024MaRDI QIDQ5641083

Seymour Papert, Robert McNaughton

Publication date: 1971

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

Modulo-counting quantifiers over finite trees, Star-free sets of integers, Unbounded fan-in circuits and associative functions, Reducing local alphabet size in recognizable picture languages, State complexity of projection on languages recognized by permutation automata and commuting letters, An extension of the wreath product principle for finite Mazurkiewicz traces, First-order logic and star-free sets, A logical approach to locality in pictures languages, Synchronizing automata preserving a chain of partial orders, Efficient algorithms for membership in Boolean hierarchies of regular languages, Constants and label-equivalence: a decision procedure for reflexive regular splicing languages, Language complexity on the synchronous anonymous ring, Pure future local temporal logics are expressively complete for Mazurkiewicz traces, Languages polylog-time reducible to dot-depth 1/2, Semigroups and languages of dot-depth two, Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors, Expressiveness and complexity of graph logic, Inverse monoids of dot-depth two, Non-elementary lower bound for Propositional Duration Calculus, On projective and separable properties, Simple splicing systems, On optimal factorization of free semigroups into free subsemigroups, Counting on CTL\(^*\): On the expressive power of monadic path logic, Schützenberger and Eilenberg theorems for words on linear orderings, Language theoretical properties of hairpin formations, Observations on the complexity of regular expression problems, Remark on the star-height-problem, Separability by piecewise testable languages is \textsc{PTime}-complete, Automata and logics over finitely varying functions, Aural pattern recognition experiments and the subregular hierarchy, Testable and untestable classes of first-order formulae, Nondeterministic state complexity of star-free languages, Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages, A uniform method for proving lower bounds on the computational complexity of logical theories, Parallel language recognition in constant time by cellular automata, On aperiodic and star-free formal power series in partially commuting variables, Synergy in machines, Classifying regular events in symbolic logic, \(\omega\)-languages accepted by finite automata whose structures are cascade products o resets, The expressivity of autosegmental grammars, Logically defined subsets of \(\mathbb{N}{}^ k\), Monadic partition logics and finite automata, On the acceptance power of regular languages, A note on the commutative closure of star-free languages, Walking on data words, Regular languages in \(NC\), Fine hierarchies and m-reducibilities in theoretical computer science, Formulas, regular languages and Boolean circuits, On noncounting regular classes, Star-free trace languages, Grammatical inference of directed acyclic graph languages with polynomial time complexity, Dynamical systems in categories, Standard automata and semidirect products of transformation semigroups, Games, equations and dot-depth two monoids, Equations and dot-depth one, Operator precedence and the visibly pushdown property, Some results on the generalized star-height problem, Local temporal logic is expressively complete for cograph dependence alphabets, On the fixpoints of monogenic functions in free monoids, Reducing the time complexity of testing for local threshold testability, The Burnside problem for semigroups, Morphic characterizations of languages in Chomsky hierarchy with insertion and locality, Descriptional and computational complexity of finite automata -- a survey, Expressive power of existential first-order sentences of Büchi's sequential calculus, Ehrenfeucht-Fraïssé goes automatic for real addition, Monoides syntactiques des langages algébriques, Star-free languages are Church-Rosser congruential, Learning in the limit with lattice-structured hypothesis spaces, On the equivalence, containment, and covering problems for the regular and context-free languages, The structure of reflexive regular splicing languages via Schützenberger constants, Logic and rational languages of words indexed by linear orderings, Regularity of sets of initial strings of periodic D0L-systems, Properties of code events and homomorphisms over regular events, Classes of languages generated by the Kleene star of a word, The dot-depth hierarchy of star-free languages is infinite, Sur le produit de concatenation non ambigu, Local testability from words to traces, a suitable definition, A combinatorial property of codes having finite synchronization delay, Characterizing the regular prefix codes and right power-bounded languages, Synchronization and simplification, Classifying regular languages by a split game, Splicing representations of stricly locally testable languages, A probabilistic approach to navigation in Hypertext, Weighted automata and multi-valued logics over arbitrary bounded lattices, Games, equations and the dot-depth hierarchy, \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata, Families of locally testable languages, Alternating finite automata and star-free languages, Optimal estimation on the order of local testability of finite automata, LANGAGE: A Maple package for automaton characterization of regular languages, Star free expressions over the reals, On relation between linear temporal logic and quantum finite automata, Dynamic linear time temporal logic, Right and left locally testable languages, Representation theorems on regular languages, Long-term memory modules, Expressive completeness of duration calculus., On the expressive power of temporal logic for infinite words, Logic over words on denumerable ordinals, On a complete set of generators for dot-depth two, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, State-complexity of finite-state devices, state compressibility and incompressibility, Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies, First-order properties of trees, star-free expressions, and aperiodicity, Polynomial closure and unambiguous product, Weighted Automata and Weighted Logics, Rational, recognizable, and aperiodic partially lossy queue languages, Star-free picture expressions are strictly weaker than first-order logic, Unnamed Item, Classes of picture languages that cannot be distinguished in the chain code concept and deletion of redundant retreats, New results on the generalized star-height problem, First-order logic on finite trees, Unnamed Item, Unnamed Item, Logical definability of some rational trace languages, Regularity Conditions for Iterated Shuffle on Commutative Regular Languages, State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs, An efficient algorithm for local testability problem of finite state automata, Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words, Positive First-order Logic on Words and Graphs, A first-order logic characterization of safety and co-safety languages, Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages, Unnamed Item, Forbidden Patterns for FO² Alternation Over Finite and Infinite Words, Unnamed Item, On the undecidability and descriptional complexity of synchronized regular expressions, Merging two hierarchies of external contextual grammars with subregular selection, On the translation of automata to linear temporal logic, A first-order logic characterisation of safety and co-safety languages, First-order separation over countable ordinals, Ramsey monoids, Relations of contextual grammars with strictly locally testable selection languages, Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars, Unnamed Item, Unnamed Item, Aperiodic String Transducers, The product of rational languages, Unnamed Item, Circuit complexity of regular languages, Reversible Regular Languages: Logical and Algebraic Characterisations, On Rough Approximations of Languages under Infinite Index Indiscernibility Relations, Properties of graphs specified by a regular language, Efficient Learning of Tier-Based Strictly k-Local Languages, The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy, On Expressive Power of Regular Expressions over Infinite Orders, Unnamed Item, On dot-depth two, The descriptive complexity approach to LOGCFL, Imre Simon: an exceptional graduate student, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Limited automata and unary languages, Associative language descriptions, Nondeterministic State Complexity of Star-Free Languages, Unnamed Item, From Monadic Logic to PSL, From LTL to Symbolically Represented Deterministic Automata, Circuit complexity and the expressive power of generalized first-order formulas, Unnamed Item, Where First-Order and Monadic Second-Order Logic Coincide, Complexity of bifix-free regular languages, Complexity of bifix-free regular languages, Circular codes and synchronization, Unnamed Item, Exposing graph uniformities via algebraic specification, Separating regular languages with two quantifier alternations, Expressive capacity of subregular expressions, Conversation and Games, On All Things Star-Free, Unnamed Item, The Quantifier Alternation Hierarchy of Synchronous Relations, Weighted Operator Precedence Languages, Invito alla teoria dei linguaggi formali, Unnamed Item, Quantifiers on languages and codensity monads, From Two-Way Transducers to Regular Function Expressions, Backward Deterministic Büchi Automata on Infinite Words, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Regulated variants of limited context restarting automata, Towards a language theory for infinite N-free pomsets., Bilateral locally testable languages., On the expressive power of temporal logic, Vectorial languages and linear temporal logic, Bounded model checking of infinite state systems, Regular sets of infinite message sequence charts, Limited Set quantifiers over Countable Linear Orderings, Weighted automata and weighted logics, On Decidability of Intermediate Levels of Concatenation Hierarchies, Accepting splicing systems with permitting and forbidding words, Functional Specification of Hardware via Temporal Logic, Unnamed Item, An aperiodicity problem for multiwords, A note on some languages in uniform \(ACC^ 0\), On uniformity within \(NC^ 1\), A characterization of constant-time cellular automata computation, First-Order Logic Definability of Free Languages, Concatenation hierarchies: new bottle, old wine, Decidability and universality of quasiminimal subshifts, Inclusion relations between some congruences related to the dot-depth hierarchy, The topological structure of adherences of regular languages, Message exchange games in strategic contexts, On the splicing operation, The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy, Aspects of Reversibility for Classical Automata, Expressive Capacity of Concatenation Freeness, Checking Whether an Automaton Is Monotonic Is NP-complete, Alternation Hierarchies of First Order Logic with Regular Predicates, Beyond operator-precedence grammars and languages, Reducing the local alphabet size in tiling systems by means of 2D comma-free codes, Synchronizing Automata Preserving a Chain of Partial Orders, The Algebraic Counterpart of the Wagner Hierarchy, On Second-Order Monadic Groupoidal Quantifiers, Language Games, Expressiveness of propositional projection temporal logic with star, Deciding FO-definability of regular languages, Quantitative vs. weighted automata, Aperiodicity in Tree Automata, Learning Left-to-Right and Right-to-Left Iterative Languages, Unnamed Item, Operator precedence temporal logic and model checking, LTL is closed under topological closure, Synchronizing Automata and the Černý Conjecture, Characterization of Logics over Ranked Tree Languages, Weak Second‐Order Arithmetic and Finite Automata, Hierarchies and reducibilities on regular languages related to modulo counting, Homomorphic characterization of tree languages based on comma-free encoding, Work-sensitive dynamic complexity of formal languages, Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order, Theory of reaction automata: a survey, An Algebraic Characterization of Strictly Piecewise Languages, Theme and Variations on the Concatenation Product, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages, Languages of dot-depth 3/2, Algebraic recognizability of regular tree languages, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Linear splicing and syntactic monoid, On the Krohn-Rhodes Cascaded Decomposition Theorem, Some properties of iterated languages, Characterizing CTL-like logics on finite trees., Finite semigroup varieties of the form V*D, Determination of finite automata accepting subregular languages, An application of the Ehrenfeucht-Fraisse game in formal language theory, Subsequence versus substring constraints in sequence pattern languages, From Philosophical to Industrial Logics, Pro-aperiodic monoids via saturated models, Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet, A sufficient condition to polynomially compute a minimum separating DFA, Learning in varieties of the form \(\mathbf {V^{*}LI}\) from positive data, A deterministic parsing algorithm for ambiguous regular expressions, The Shuffle Product: New Research Directions, Descriptional and Computational Complexity of Finite Automata, New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality, Quantifier Alternation for Infinite Words, Aperiodic String Transducers, Factorization Forests, Splicing Systems: Accepting Versus Generating, Expressive Completeness for LTL With Modulo Counting and Group Quantifiers, Generic results for concatenation hierarchies, Weighted operator precedence languages, Dot-depth of star-free events, Codensity, profiniteness and algebras of semiring-valued measures, Locally testable languages, Syntactic complexity of bifix-free regular languages, Characterizations of locally testable events, An axiomatization of PCTL*, A reducibility for the dot-depth hierarchy, Boolean algebras of regular languages, Counting modulo quantifiers on finite structures, An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic, Star-free sets of words on ordinals, Languages defined with modular counting quantifiers, The many faces of a translation, The alphabetic complexity in homomorphic definitions of word, tree and picture languages, A conjecture on the concatenation product, Omega-rational expressions with bounded synchronization delay, Regularity conditions for iterated shuffle on commutative regular languages, State complexity of permutation and related decision problems on alphabetical pattern constraints, Concatenation-free languages