Arthur MILCHIOR

Hello

I have a PhD in computer science from Université Paris Diderot. I was a PostDoc in the Computer Science lab Université_libre_de_Bruxelles. Googler between May 2020 and May 2021. I am also a maintainer of Ankidroid and contributor to the anki ecosystem.

I'm trying to take time to write down into wikipedia the missing information of my field, when I learn them and see they are not currently in wikipedia.

Else I'm also a stand-up comedian [[1]] and blogger [[2]]

Creation

Model Checking

• Timed word
• Signal (model checking)
• Metric interval temporal logic
• Timed propositional temporal logic
• Clock (model checking)
• Signal automaton
• Alternating timed automaton
• Region (Model checking)

Complexity

Turing Machine

• Random-access Turing machine
• Configuration graph
• Logarithmic time hierarchy
• Padding argument, it was a red link on the Immerman–Szelepcsényi theorem page.
• Unambiguous Turing machine

Automata

• Weak Büchi automaton
• Unambiguous finite automaton
• Channel system (computer science)

Descriptive complexity

• Second order in descriptive complexity/finite model theory.
• High order in descriptive complexity/finite model theory. There are results I know but that I can not write in this article, because they only are in an article I wrote and not yet submitted to a journal.
• First order in descriptive complexity/finite model theory. The article existed before me but was only a stub.

Circuit complexity

• Circuit (computer theory) because before me wikipedia knew only the boolean circuits
• Integer circuit
• Circuits over sets of natural numbers

Logic

• Büchi arithmetic
• Skolem arithmetic and its disambiguation page

Algorithmic

• Persistent array
• Sparse representations of numbers
• Purely functional datastructure
• Purely functional programming
• Real-time queue and amortized queue
• Real-time deque
• Difference bound matrix
• Measure of presortedness and M-optimal sorting
• K-sorted sequence and K-sorting
• Run of a sequence

Semigroup theory

• recognizable set
• rational set
• nilsemigroup
• Profinite words
• Variety of finite semigroups
• Regular numerical predicate

Other

• Multiplicative independence
• Autocorrelation (words)

Non trivial changes

• ELEMENTARY I gave the descriptive complexity caracterisation of this complexity class.
• Linear logic
• L (complexity)
• bounded alternating Turing machine
• Nested word
• Thompson's construction algorithm
• Presburger_arithmetic#Presburger-definable_integer_relation Characterization of the Presburger-definable sets.
• Skew binary number system
• Lexicographic breadth-first search Explaining the word Lexicographic, characterizing the LexBFS orders.
• Quotients and divisions of semigroups
• Generating set of a semigroup/monoid
• Graded monoid
• Special classes of semigroups (Adding the variety column, and some examples from Pin's textbook)
• Specification and specifiable classes in analytic combinatorics
• Metric temporal logic (everything except the intro)
• Timed automaton
• Communicating finite-state machine formal definition and relation to Channel System

Translations

• Glushkov's construction algorithm

A few modification

• Finite model property
• Recursively enumerable language
• Mealy machine (which surprises me because even if the history page assert that I wrote a paragraph, I don't remember doing it, nor do I remember that I ever worked one day with those machines, and I don't know anymore anything of what I added)
• Reflected polynomial (Mostly stating that some author use this name instead of the more standard one.)