On the public citation graph

Logic, semigroups and automata on words

https://doi.org/10.1007/bf02127803
0 signed · 133 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/malq.19600060105openalex-snapshot
Weak Second‐Order Arithmetic and Finite Automata
inferredcites →https://doi.org/10.1007/3-540-07407-4_23openalex-snapshot
Piecewise testable events
inferredcites →https://doi.org/10.1007/3-540-15641-0_21openalex-snapshot
Ensembles reconnaissables de mots bi-inpinis Limite et déterminisme
inferredcites →https://doi.org/10.1007/3-540-16078-7_75openalex-snapshot
Varietes de Semis Groupes et Mots Infinis
inferredcites →https://doi.org/10.1007/3-540-16761-7_79openalex-snapshot
Etude syntaxique des parties reconnaissables de mots infinis
inferredcites →https://doi.org/10.1007/3-540-19488-6_142openalex-snapshot
Regular languages defined with generalized quantifiers
inferredcites →https://doi.org/10.1007/3-540-54233-7_154openalex-snapshot
On logics, tilings, and automata
inferredcites →https://doi.org/10.1007/3-540-54233-7_166openalex-snapshot
An EILENBERG theorem for ∞-languages
inferredcites →https://doi.org/10.1007/3-540-56503-5_60openalex-snapshot
Locally threshold testable languages of infinite words
inferredcites →https://doi.org/10.1007/3-540-56610-4_89openalex-snapshot
On the Ehrenfeucht-Fraïssé game in theoretical computer science
inferredcites →https://doi.org/10.1007/3-540-60084-1_87openalex-snapshot
Polynomial closure and unambiguous product
inferredcites →https://doi.org/10.1007/978-1-4613-8928-6_22openalex-snapshot
Weak Second-Order Arithmetic and Finite Automata
inferredcites →https://doi.org/10.1007/978-1-4613-8928-6_23openalex-snapshot
On a Decision Method in Restricted Second Order Arithmetic
inferredcites →https://doi.org/10.1007/978-1-4613-8928-6_26openalex-snapshot
Definability in the Monadic Second-Order Theory of Successor
inferredcites →https://doi.org/10.1007/978-3-662-36678-3openalex-snapshot
Büchi’s Monadic Second Order Successor Arithmetic
inferredcites →https://doi.org/10.1007/bf00299636openalex-snapshot
The method of forced enumeration for nondeterministic automata
inferredcites →https://doi.org/10.1007/bf01691063openalex-snapshot
Decision problems forω-automata
inferredcites →https://doi.org/10.1007/bf01761708openalex-snapshot
Algebraic decision procedures for local testability
inferredcites →https://doi.org/10.1007/bf02573578openalex-snapshot
Some results on the dot-depth hierarchy
inferredcites →https://doi.org/10.1007/bf02679467openalex-snapshot
Polynomial closure and unambiguous product
inferredcites →https://doi.org/10.1007/bfb0015728openalex-snapshot
About rational sets of factors of a bi-infinite word
inferredcites →https://doi.org/10.1007/bfb0030294openalex-snapshot
Recent results on automata and infinite words
inferredcites →https://doi.org/10.1007/bfb0035752openalex-snapshot
Factors of words
inferredcites →https://doi.org/10.1007/bfb0036941openalex-snapshot
Varietes de semigroupes et mots infinis
inferredcites →https://doi.org/10.1007/bfb0039607openalex-snapshot
Polynomial operations on rational languages
inferredcites →https://doi.org/10.1007/bfb0064872openalex-snapshot
Weak monadic second order theory of succesor is not elementary-recursive
inferredcites →https://doi.org/10.1016/0021-8693(88)90067-1openalex-snapshot
Partially ordered finite monoids and a theorem of I. Simon
inferredcites →https://doi.org/10.1016/0022-0000(78)90049-1openalex-snapshot
The dot-depth hierarchy of star-free languages is infinite
inferredcites →https://doi.org/10.1016/0022-0000(82)90016-2openalex-snapshot
Classifying regular events in symbolic logic
inferredcites →https://doi.org/10.1016/0022-0000(86)90037-1openalex-snapshot
First-order logic and star-free sets
inferredcites →https://doi.org/10.1016/0022-0000(93)90005-hopenalex-snapshot
On the expressive power of temporal logic
inferredcites →https://doi.org/10.1016/0022-4049(79)90025-2openalex-snapshot
Aperiodic homomorphisms and the concatenation product of recognizable sets
inferredcites →https://doi.org/10.1016/0022-4049(85)90071-4openalex-snapshot
Graph congruences and wreath products
inferredcites →https://doi.org/10.1016/0022-4049(91)90019-xopenalex-snapshot
Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon
inferredcites →https://doi.org/10.1016/0097-3165(86)90061-0openalex-snapshot
On a natural extension of Jacob's ranks
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(84)90095-1openalex-snapshot
Bilimites de langages reconnaissables
inferredcites →https://doi.org/10.1016/0304-3975(85)90003-9openalex-snapshot
Characterizations of some classes of regular events
inferredcites →https://doi.org/10.1016/0304-3975(85)90148-3openalex-snapshot
A syntactic congruence for rational ω-languages
inferredcites →https://doi.org/10.1016/0304-3975(88)90034-5openalex-snapshot
Semigroups and languages of dot-depth two
inferredcites →https://doi.org/10.1016/0304-3975(89)90151-5openalex-snapshot
Inverse monoids of dot-depth two
inferredcites →https://doi.org/10.1016/0304-3975(90)90047-lopenalex-snapshot
Factorization forests of finite height
inferredcites →https://doi.org/10.1016/0304-3975(91)90075-dopenalex-snapshot
Finite-automaton aperiodicity is PSPACE-complete
inferredcites →https://doi.org/10.1016/0304-3975(91)90258-4openalex-snapshot
Languages and scanners
inferredcites →https://doi.org/10.1016/0304-3975(91)90268-7openalex-snapshot
Opérations polynomiales et hiérarchies de concaténation
inferredcites →https://doi.org/10.1016/0304-3975(91)90281-6openalex-snapshot
On the expressive power of temporal logic for infinite words
inferredcites →https://doi.org/10.1016/0304-3975(92)90121-uopenalex-snapshot
On a conjecture concerning dot-depth two languages
inferredcites →https://doi.org/10.1016/0304-3975(93)90218-iopenalex-snapshot
Finite-model theory - a personal perspective
inferredcites →https://doi.org/10.1016/b978-0-12-198820-3.50008-5openalex-snapshot
ON RICH WORDS
inferredcites →https://doi.org/10.1016/b978-0-444-88074-1.50006-8openalex-snapshot
Finite Automata
inferredcites →https://doi.org/10.1016/b978-0-444-88074-1.50009-3openalex-snapshot
Automata on Infinite Objects
inferredcites →https://doi.org/10.1016/b978-0-444-88074-1.50021-4openalex-snapshot
Temporal and Modal Logic
inferredcites →https://doi.org/10.1016/s0012-365x(73)80005-6openalex-snapshot
Characterizations of locally testable events
inferredcites →https://doi.org/10.1016/s0019-9958(65)90108-7openalex-snapshot
On finite monoids having only trivial subgroups
inferredcites →https://doi.org/10.1016/s0019-9958(66)80013-xopenalex-snapshot
Testing and generating infinite sequences by a finite automaton
inferredcites →https://doi.org/10.1016/s0019-9958(77)90443-0openalex-snapshot
Application of model theoretic games to discrete linear orders and finite automata
inferredcites →https://doi.org/10.1016/s0019-9958(79)90629-6openalex-snapshot
Star-free regular sets of ω-sequences
inferredcites →https://doi.org/10.1016/s0019-9958(81)90663-xopenalex-snapshot
A combinatorial approach to the theory of ω-automata
inferredcites →https://doi.org/10.1016/s0019-9958(85)80058-9openalex-snapshot
Complexity of some problems from the theory of automata
inferredcites →https://doi.org/10.1016/s0049-237x(08)71879-2openalex-snapshot
On Local and Non-Local Properties
inferredcites →https://doi.org/10.1051/ita/1984180100231openalex-snapshot
Hiérarchies de concaténation
inferredcites →https://doi.org/10.1070/im1980v015n02abeh001252openalex-snapshot
ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
inferredcites →https://doi.org/10.1090/s0002-9947-1961-0139530-9openalex-snapshot
Decision problems of finite automata design and related arithmetics
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1112/blms/12.3.230bopenalex-snapshot
SEMIGROUPS AND COMBINATORIAL APPLICATIONS
inferredcites →https://doi.org/10.1112/plms/s2-30.1.264openalex-snapshot
On a Problem of Formal Logic
inferredcites →https://doi.org/10.1137/0216051openalex-snapshot
Languages that Capture Complexity Classes
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1142/s0218196793000263openalex-snapshot
INVERSE MONOIDS OF DOT-DEPTH TWO
inferredcites →https://doi.org/10.1142/s0218196793000287openalex-snapshot
AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
inferredcites →https://doi.org/10.1145/567446.567462openalex-snapshot
On the temporal analysis of fairness
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1515/9781400882618-002openalex-snapshot
Representation of Events in Nerve Nets and Finite Automata
inferredcites →https://doi.org/10.2307/2268308openalex-snapshot
Concatenation as a basis for arithmetic
inferredcites →https://doi.org/10.2307/2271090openalex-snapshot
Definability in the monadic second-order theory of successor
inferredcites →https://doi.org/10.4153/cjm-1986-025-6openalex-snapshot
Ensembles Reconnaissables de Mots Biinfinis

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/malq.201400113openalex-snapshot
Locally finite ω‐languages and effective analytic sets have the same topological complexity
inferred← citeshttps://doi.org/10.1006/inco.2000.3009openalex-snapshot
Star-Free Sets of Words on Ordinals
inferred← citeshttps://doi.org/10.1007/11672142_24openalex-snapshot
On the Accepting Power of 2-Tape Büchi Automata
inferred← citeshttps://doi.org/10.1007/3-540-45066-1_12openalex-snapshot
On Infinitary Rational Relations and Borel Sets
inferred← citeshttps://doi.org/10.1007/3-540-58201-0_87openalex-snapshot
Polynomial closure of group languages and open sets of the Hall topology
inferred← citeshttps://doi.org/10.1007/3-540-60084-1_87openalex-snapshot
Polynomial closure and unambiguous product
inferred← citeshttps://doi.org/10.1007/3-540-61440-0_137openalex-snapshot
The expressive power of existential first order sentences of büchi's sequential calculus
inferred← citeshttps://doi.org/10.1007/978-3-030-30229-0_3openalex-snapshot
The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings
inferred← citeshttps://doi.org/10.1007/978-3-032-28404-4_3openalex-snapshot
Seventy Years of Algebraic, Logical, and Topological Methods for Regular Languages
inferred← citeshttps://doi.org/10.1007/978-3-540-25984-8_16openalex-snapshot
Second-Order Logic over Finite Structures – Report on a Research Programme
inferred← citeshttps://doi.org/10.1007/978-3-540-28629-5_8openalex-snapshot
Algebraic Recognizability of Languages
inferred← citeshttps://doi.org/10.1007/978-3-540-69407-6_11openalex-snapshot
The Algebraic Counterpart of the Wagner Hierarchy
inferred← citeshttps://doi.org/10.1007/978-3-540-70583-3_20openalex-snapshot
Tree Languages Defined in First-Order Logic with One Quantifier Alternation
inferred← citeshttps://doi.org/10.1007/978-3-642-15025-8_13openalex-snapshot
The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
inferred← citeshttps://doi.org/10.1007/978-3-642-21493-6_3openalex-snapshot
Theme and Variations on the Concatenation Product
inferred← citeshttps://doi.org/10.1007/978-3-642-59136-5_10openalex-snapshot
Syntactic Semigroups
inferred← citeshttps://doi.org/10.1007/978-94-011-0149-3_1openalex-snapshot
Finite Semigroups and Recognizable Languages: An Introduction
inferred← citeshttps://doi.org/10.1007/978-94-011-0149-3_3openalex-snapshot
Semigroups and Automata on Infinite Words
inferred← citeshttps://doi.org/10.1007/bf02679467openalex-snapshot
Polynomial closure and unambiguous product
inferred← citeshttps://doi.org/10.1007/bfb0054312openalex-snapshot
Positive varieties and infinite words
inferred← citeshttps://doi.org/10.1007/bfb0055073openalex-snapshot
Bridges for concatenation hierarchies
inferred← citeshttps://doi.org/10.1007/pl00001594openalex-snapshot
Monadic logical definability of nondeterministic linear time
inferred← citeshttps://doi.org/10.1007/s00153-008-0101-7openalex-snapshot
Topological complexity of locally finite ω-languages
inferred← citeshttps://doi.org/10.1007/s41980-018-0142-6openalex-snapshot
On Ideals of Quasi-Commutative Semigroups
inferred← citeshttps://doi.org/10.1016/j.disc.2004.04.027openalex-snapshot
Expressive power of existential first-order sentences of Büchi's sequential calculus
inferred← citeshttps://doi.org/10.1016/j.ipl.2008.05.012openalex-snapshot
A note on partially ordered tree automata
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.03.025openalex-snapshot
Closure properties of locally finite ω-languages
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.07.017openalex-snapshot
Efficient algorithms for membership in boolean hierarchies of regular languages
inferred← citeshttps://doi.org/10.1016/s0079-8169(04)80014-xopenalex-snapshot
References
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00230-4openalex-snapshot
Algebraic tools for the concatenation product
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00120-xopenalex-snapshot
Polynomial closure of group languages and open sets of the Hall topology
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00286-8openalex-snapshot
Locally finite languages
inferred← citeshttps://doi.org/10.1016/s1570-2464(07)80022-xopenalex-snapshot
19 Applications of modal logic in linguistics
inferred← citeshttps://doi.org/10.1051/ita/2009004openalex-snapshot
A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I
inferred← citeshttps://doi.org/10.1051/ita:2003013openalex-snapshot
Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
inferred← citeshttps://doi.org/10.1051/ita:2003016openalex-snapshot
On the Topological Complexity of Infinitary Rational Relations
inferred← citeshttps://doi.org/10.1051/ita:2003017openalex-snapshot
Regular languages definable by Lindström quantifiers
inferred← citeshttps://doi.org/10.1051/ita:2007050openalex-snapshot
On the continuity set of an Omega rational function
inferred← citeshttps://doi.org/10.1081/agb-120016749openalex-snapshot
Tameness of Some Locally Trivial Pseudovarieties
inferred← citeshttps://doi.org/10.1109/lics.1998.705640openalex-snapshot
Existential second-order logic over strings
inferred← citeshttps://doi.org/10.1109/lics.2007.51openalex-snapshot
Two-way unary temporal logic over trees
inferred← citeshttps://doi.org/10.1142/s0129054108005802openalex-snapshot
A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
inferred← citeshttps://doi.org/10.1142/s0218196710005595openalex-snapshot
ALGEBRAIC CHARACTERIZATION OF LOGICALLY DEFINED TREE LANGUAGES
inferred← citeshttps://doi.org/10.1145/1376916.1376925openalex-snapshot
Effective characterizations of tree logics
inferred← citeshttps://doi.org/10.1145/1501434.1501480openalex-snapshot
Execution monitoring enforcement for limited-memory systems
inferred← citeshttps://doi.org/10.1145/331605.331609openalex-snapshot
Existential second-order logic over strings
inferred← citeshttps://doi.org/10.2168/lmcs-3(1:4)2007openalex-snapshot
Logic Meets Algebra: the Case of Regular Languages
inferred← citeshttps://doi.org/10.2168/lmcs-5(3:5)2009openalex-snapshot
Two-Way Unary Temporal Logic over Trees
inferred← citeshttps://doi.org/10.2168/lmcs-6(4:1)2010openalex-snapshot
Tree Languages Defined in First-Order Logic with One Quantifier Alternation
inferred← citeshttps://doi.org/10.3390/math9050491openalex-snapshot
Prime i-Ideals in Ordered n-ary Semigroups
inferred← citeshttps://doi.org/10.48550/arxiv.0801.3912openalex-snapshot
On the Continuity Set of an omega Rational Function
inferred← citeshttps://doi.org/10.48550/arxiv.0802.2868openalex-snapshot
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages
inferred← citeshttps://doi.org/10.48550/arxiv.1202.3355openalex-snapshot
Lattices of Logical Fragments over Words
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9809118openalex-snapshot
The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy
inferred← citeshttps://doi.org/10.70675/984fba72z6266z4f52z9948z528cadd946cbopenalex-snapshot
Decidable characterizations for tree logics
inferred← citeshttps://doi.org/10.70675/ab8c4538zf338z4b1dzb5c4z539a6179abc8openalex-snapshot
A study on the expressive power of some fragments of the modal µ-calculus
inferred← citeshttps://doi.org/10.7146/brics.v10i28.21796openalex-snapshot
Regular Languages Definable by Lindström Quantifiers
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.